본문 바로가기

알고리즘 이론/유클리드 알고리즘1

최대공약수(유클리드 알고리즘)와 최소공배수 찾기 - 유클리드 알고리즘: 최대 공약수 찾기 알고리즘 - 최대 공약수(GCD, Greatest Common Divisor): 1번: 재귀 함수 이용 def gcd(a, b): return a if b == 0 else gcd(b, a%b) print(gcd(6, 24)) # 6 2번: 재귀 함수 X def gcd2(a, b): gcd = 1 for k in range(2, min(a, b) + 1): while a % k == 0 and b % k == 0: a //= k b //= k gcd *= k return gcd def lcm(a, b): return a*b//gcd2(a, b) print(gcd2(14, 42)) # 14 print(lcm(14, 42)) # 42 - 출처: m.blog.naver.. 2020. 10. 14.

티스토리툴바