2609_ 최대공약수와 최소공배수

문제는 더보기!

 

최대공약수와 최소공배수

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

53055

31360

25447

60.539%

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1 복사

24 18

예제 출력 1 복사

6
72

 

슬프게도 문제를 풀려면 자력으로는 힘들고 수학적 지식이 있어야한다.

 

물론 최대,최소공약수 푸는방법을 알기에 1~10000까지의 소수리스트를 만들어서 손으로 계산하듯이 풀 수도 있겠지만

 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

유클리드 호제법이란 것을 알아야 문제에 쉽게 접근할 수 있다.

 

 a,b라는 숫자가있다면 a를 b로 나눈 나머지값을 r이라고 생각해보자. a와 b의 최대공약수는 b와 r간의 최대공약수와 같다. 그리고 r의값이 0이나올때까지 반복한다면 그때 나눈 수가 최대공약수가 된다.

 

최소공배수는 a,b 두수의 곱을 최대공약수로 나눈 값이다.

 

a,b = map(int,input().split())

def gcd(a,b):
    while b > 0 :
        a,b = b, a % b
    return a

def lcm(a,b):
    return a*b // gcd(a,b)

print(gcd(a,b))
print(lcm(a,b))