백준 / 최대공약수와 최소공배수 / 2609

Question

문제링크
Silver 5

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

Input

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

24 18

Output

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

6
72

Logic

기본 구조 : 유클리드 호제법
1. 두 수 n,m을 큰 수 nn,작은수 mm으로 나눈다.
2. 큰 수를 작은수로 나눈다.
3. 작은 수를 방금 계산한 나머지 modd로 다시 나눈다.
4. 이 과정을 나머지가 0이 될 때 까지 반복한다.
5. 계산이 끝난 후 mm가 최대공약수이다.
6. 계산이 끝난 후 mm(n//mm) (m//mm) 가 최소공배수이다.

Code

data=input().split()
n,m=int(data[0]),int(data[1])
nn,mm=max(n,m),min(n,m)

modd=nn%mm
while modd:
    nn=mm    
    mm=modd
    modd=nn%mm
print(mm)
print(mm*(n//mm)*(m//mm))