최소공배수
-
[Python] 백준 2609 최대공약수와 최소공배수Python_알고리즘 2021. 7. 11. 02:27
문제 바로가기 문제분석 # 유클리드 호제법으로 최대공약수를 구한 후, 그걸 힌트로 최소공배수를 구한다. a,b의 최대공약수 == b와 a%b의 최대공약수 a%b가 0이 될 경우(나머지가 없이 a가 b로 딱 떨어진다는 것이므로) b가 최대공약수 최소공배수는 두 값의 곱/최대공약수 # 유클리드 호제법의 예 24 - 1 2 3 4 6 8 12 24#24의 약수들 18 - 1 2 3 6 9 18# 18의 약수들 a = 24 b = 18 a, b = b , a % b 24, 18 = 18, 6 18, 6 = 6, 0 -> 나머지가 0이 되었으니 나누는 수 6이 24와 18의 최대공약수 문제풀이 a, b = map(int, input().split()) def gcd(a, b): while b > 0: a, b =..