프로그램 5-1
최대공약수를 구하는 알고리즘
◉ 예제 소스 p05-1-gcd.py
# 최대공약수 구하기
# 입력: a, b
# 출력: a와 b의 최대공약수
def gcd(a, b):
i = min(a, b) # 두 수 중에서 최솟값을 구하는 파이썬 함수
while True:
if a % i = = 0 and b % i = = 0:
return i
i = i - 1 # i를 1만큼 감소시킴
print(gcd(1, 5)) # 1
print(gcd(3, 6)) # 3
print(gcd(60, 24)) # 12
print(gcd(81, 27)) # 27
TIP
a %i = =0에서 %는 나머지를 구하는 연산자입니다. 즉, a를 i로 나누었을 때 나머지가 0이면 a는 i로 나누어떨어진다는 의미입니다.
실행 결과
1
3
12
27