[단계별로 풀어보기][python3] 정수론 및 조합론 - 최대 공약수 최소 공배수

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

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

최대 공약수와 최소 공배수를 구하는 문제다.

a, b = map(int, input().split())

for i in range(1, a*b+1):
    if a%i == 0 and b%i == 0:
        mg = i
    if i%a == 0 and i%b == 0:
        mb = i
        break

print(mg)
print(mb)

위와 같이 for문을 돌려서 최소 공배수와 최대공약수를 알아낼 수도 있다.

그런데 위의 코드는 pypy3을 통해서만 겨우 시간안에 통과가 가능하다.

최대공약수와 최소공배수

최대공약수(GCD. Greatest Common Division)와 최소공배수(LCM. Least Common Multiple)는 다음과 같은 성질을 가진다.

어떤 자연수 A와 B의 최대공약수가 G, 최소공배수가 L이라고 할 경우

A * B = G * L

그 이유는 다음과 같이 벤 다이어 그램으로 설명 가능하다.

출처: 15장 - 집합과 명제(1) : 네이버 블로그 (naver.com)

A * B = {a, b, c, d, c, d, e}

G = {a, b, c, d, e}

L = {c, d}

G * L = {a, b, c, d, c, d, e}

유클리드 호제법

출처: 나무위키 ㅎㅎ;;

우리나라 교육과정에서는 나오지 않지만 알아두면 편리한 유클리드 호제법이다.

위와같이 a와 b가 주어졌을 때 gcd(a,b)는 gcd(b, r)과 같으며 r은 a%b이다.

따라서 저거를 반복문으로 돌리면 최대공약수가 구해진다는 소리다.

def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

따라서 최소공배수(LCM)은 다음처럼 구할 수 있다.

LCM = a * b / gcd(a, b)

풀이

def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

a, b = map(int, input().split())

g = int(gcd(a, b))
l = int(a*b/g)

print(g)
print(l)

아래 풀이는 for문을 돌렸을 때고, 위의 풀이는 유클리드 호제법을 적용한 방식이다.