[BOJ-2609]최대공약수와 최소공배수

두 개의 자연수를 입력받아 

1) 최대공약수

2) 최소공배수

출력하는 프로그램을 작성하는 것인데

유클리드 호제법으로도 풀어야 하는데

그냥 이렇게 풀면 되겠다 싶어서 해봤다.

1) 두 수를 공통적으로 나눌 수 있는 소수(Prime Number)가 있다.

2) 두 수를 다 나눈다. 그리고 나눈 소수를 공통으로 모아둔다.

3) 이 과정을 반복해서 문제에서 주어진 10000 이하 자연수까지 입력이므로, 10000까지 진행한다.

4) 최대공약수는 공통으로 나눈 소수를 모아둔 변수를 출력한다.

5) 최소공배수는 최대공약수에 끝까지 나눠진 두수를 곱한다

num = map(int,raw_input().split())
 
GCD = 1
for div in range(2,10000+1):
    while(num[0] % div == 0 and num[1] % div == 0):
        num[0] /= div
        num[1] /= div
        GCD *= div
 
print GCD
print GCD*num[0]*num[1]