#2609 최대공약수 최소공배수 [백준](H99.16)
📄문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
예제 입력1
24 18
예제 출력1
6 72
🖋️코드
a, b = map(int, input().split())
def gcd(a, b):
if a > b:
while b > 0:
a , b = b , a % b
return a
else:
while a > 0:
b , a = a , b % a
return b
def lcm(a, b):
return a * b // gcd(a, b)
print(gcd(a, b))
print(lcm(a, b))
🧷(나만 알아듣는) 추가설명
처음에는 각 숫자의 공약수들을 따로 list로 담아서 공집합으로 같은것중 가장 높은 수를 프린트 하는 방식을 사용했지만 효율적이지 않은거 같다.
"유클리드 호제법" 으로 풀면 간단해진다.
a를 b로 나눈 나머지를 c 이라고 했을 때, a와 b의 최대공약수는 b와 c의 최대공약수이다.
즉, a와 b의 최대공약수는 b와 a%b의 최대공약수이다. (신기..)
그리고 최소공배수는 a * b / 최대공약수이다. (더 신기..)
Author And Source
이 문제에 관하여(#2609 최대공약수 최소공배수 [백준](H99.16)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dennis9352/2609-최대공약수-최소공배수백준H99.12저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)