[알고리즘 일기] 30. 최대 공약수 구하기

728x90

 

문제 30. (2021-05-30)

 

최대공약수 구하기

2623(Codeup). 최대 공약수 구하기

카드 두 정수 a, b를 입력받아서, a, b의 최대공약수를 출력하시오.

 

 

입력

정수 a, b가 공백으로 구분되어 입력된다.(1<=a,b<=10,000)

 

 

출력

a, b의 최대공약수를 출력한다.

 

 

❧ 테스트 셋

64
128

 

❧ 출력 예시

64

 

---

❧ 정답

A, B = input().split()
A = int(A)
B = int(B)
if A > B:
  A, B = B, A
C = A % B
while C > 0:
  gcd = C
  A, B = B, C
  C = A % B
print(gcd)

 

1️⃣ 유클리드 호제법 사용

2️⃣ 소수를 구하는 방법 사용 시, 시간 복잡도 : O(n)

3️⃣ 유클리드 호제법 사용 시, 시간 복잡도 : O(logn)

유클리드 호제법

메모리	시간	언어	길이
27724 KB	16 MS	Python	148 B