[알고리즘] 백준 파이썬 2609 최대공약수와 최소공배수

 

 

 

 

https://www.acmicpc.net/problem/2609

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

 

 

🤔 유클리드 호제법이란?

유클리드 호제법 공식
임의의 두 자연수 a, b가 주어졌을 때, 둘 중 큰 값을 a라고 가정한다.
a를 b로 나눈 나머지를 n이라고 한다면(a % b = n), n(나머지)이 0일때, b가 최대 공약수(GCD)이다.
만약 n이 0이 아니라면, a에 b값을 다시 넣고 n(나머지)를 b에 대입한 후 n이 0이 될 때까지 a % b를 반복한다. 

 

✔︎ 최대공약수를 유클리드 호제법을 활용해 계산해보기

 

✍️ 106, 52일 경우 (a = 106, b= 52)

- 106을 52로 나누었을 때 나누어 떨어진다면 52가 최대공약수이겠지만, 나누어 떨어지지 않음

- 나머지가 0일 때까지 다음과 같은 방법을 반복 

 

- 106을 52로 나눈 나머지 -> 2

- 여기서 52를 a로 가져오고 2를 b로 가져와서 a % b = n으로 계속 계산한다. n=0이 될 때까지 나눠주면 된다.

- 52를 2로 나눈 나머지 -> 0

-> 나머지가 0이므로 윗 줄에서 b인 2를 가져와서 최대공약수는 2

 

 

✍️ 721, 372일 경우 (a = 721, b= 372)

- 721을 372로 나누었을 때 나누어 떨어진다면 372가 최대공약수이겠지만, 나누어 떨어지지 않음

- 나누어 질 때까지 다음과 같은 방법을 반복

 

- 721를 372로 나눈 나머지 -> 349

- 여기서 372를 a로 가져오고 349를 b로 가져와서 a % b = n으로 계속 계산한다. n=0이 될 때까지 나눠주면 된다.

- 372를 349로 나눈 나머지 -> 23

- 349를 23으로 나눈 나머지 -> 4

- 나누어 떨어지지 않아서 계속 반복

.

.

.

최대공약수는 1

 

✔︎ 최소공배수 계산 방법

 

최소공배수 -> a, b 공통의 배수 중에 최소 값을 의미. 따라서, 둘의 배수(a*b 곱하면 무조건 둘의 배수)를 위에 구해놓은 최대 공약수로 나누면 최소 값인 배수를 구할 수 있다. 

따라서, a*b // 위의 최대 공약수 

 

답 = 윗 줄에서 구한 몫

 

 

✍️ 답

import sys
a, b = map(int, sys.stdin.readline().split())

# 유클리드 호제법
def gcd(a, b): #최대공약수
    remainder = a % b
    while remainder > 0:
        a = b
        b = remainder
        remainder = a % b
    return b    
    
def lcm(a, b): #최소공배수
    return a * b // gcd(a, b) # 곱한 값에서 최대공약수를 나눈 몫 

print(gcd(a, b))
print(lcm(a, b))

 

✔︎ 최대공약수 구하기

a % b를 한다.

나머지가 0이 아닐 때 ( 나머지 > 0), a에 b 대입. b에는 나머지 대입.

계속 반복하다가 나머지가 0일 때 최대공약수는 b이다.

 

✔︎ 최소공배수 구하기

최소 공배수는 공통의 배수 중에 가장 작은 값.

a*b는 무조건 둘의 배수임.

때문에 a*b를 공통의 약수 중 가장 큰 값(최대공약수 -> 아까 구한 거 활용)로 나누면 된다.

그래서, a * b 해주고 최대공약수로 나눠준다.