백준 2609 파이썬 최대공약수와 최소공배수

차근차근 풀었는데 시간 초과가 떴다.

약수를 하나하나 넣고 배수를 하나하나 넣어서 해서 시간이 너무 오래걸린듯

 

import sys

x, y = sys.stdin.readline().split()
x = int(x)
y = int(y)

factor_x = [x]
for i in range(1, x//2 + 1):
    if x % i == 0:
        factor_x.append(i)

factor_y = [y]
for i in range(1, y//2 + 1):
    if y % i == 0:
        factor_y.append(i)

common_f = []
for i in factor_y:
    if i in factor_x :
        common_f.append(i)

mul = []
for i in range(max(x, y), x * y + 1):
    if i % x == 0 and i % y == 0 :
        mul.append(i)

print(max(common_f))
print(min(mul))

 

 

 

 

유클리드 호제법을 이용해서 풀면 빠르게 풀린다.

 

a와 b 두 수가 있다고 할 때, 

a와 b의 최대공약수는 b와 a % b(a를 b로 나눈 나머지)의 최대공약수와 같다는 것이다.

 

예를 들어,

최대공약수(24, 18) = 최대공약수(18, 6) = 최대공약수(6, 0)가 되어

결국 둘의 최대공약수는 6이 되는 것

 

최소공배수는 

a * b를 최대공약수로 나눈 수가 된다.

import sys

x, y = map(int, sys.stdin.readline().split())


# 최대공약수 구하기
def GCD(a, b):
    A = a
    while b > 0:
        a = b
        b = A % b
        A = a
    return a


# 최소공배수 구하기
def LCM(a, b):
    return a * b // GCD(a, b)


print(GCD(x, y))
print(LCM(x, y))