백준 - 2609 - 최대공약수와 최소공배수 - Python/유클리드 호제법

2609번: 최대공약수와 최소공배수 (acmicpc.net)

2609번: 최대공약수와 최소공배수

문제

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

입력

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

출력

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

 

 

풀이

간만에 맞췄다 유클리드는 찾아봄

def gcd(x,y):
    #y가 0이 될 때까지 반복
    while y:
        #y를 x에 대입
        #x를 y로 나눈 나머지를 y에 대입
        x,y=y,x%y
    return x

a,b=map(int, input().split()) #숫자 두개 입력하는거 또 어려움

m=gcd(a,b)

print(m)
print(m*a//m*b//m)

 

사용된 개념

 

[Python] 최대공약수, 최소공배수, N개의 최소공배수 :: 개인적인공간 (tistory.com)

[Python] 최대공약수, 최소공배수, N개의 최소공배수