[백준] 2609번 최대공약수와 최소공배수 - Python

문제

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

입력

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

출력

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

예제 입출력

풀이방법

N,X = map(int, input().split())


def gcd(N,X) :
    while X > 0 :
        N, X = X, N % X
    return N

def lcm(N,X) :
    result = (N*X) // gcd(N,X)
    return result
    
print(gcd(N,X))
print(lcm(N,X))

• N을 X로 나누어서 X를 N에, N을 X로 나눈 나머지를 X에 대입시킨다
• X가 0이 될 때까지 반복을 하게되면, 남는 N 값이 최대 공약수
• N * X를 최대공약수로 나눈 몫이 최소 공배수이다

처음에 for문을 이용해서 풀었더니 계속 시간초과가 떠서...
유클리드 호제법 이라는 방법을 통해서 풀었다

유클리드 호제법

x,y의 최대 공약수는 y, r의 최대공약수와 같다는 원리를 이용하는 것
x%y == r (x를 y로 나눈 나머지 값 == r)
x와 y의 최대 공약수 == y와 r의 최대공약수

즉 계속해서 x에는 y값을 대입하고 y에는 (x%y)값인 r을 대입하다 보면 언젠가는
x % y == 0 일 때가 있다

다른 풀이방법

import math
n,x = map(int, input().split())

print(math.gcd(n,x))
print(math.lcm(n,x))

그냥 math 모듈을 이용해도 된다

---

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