백준 2609 [파이썬] (유클리드호제)

#1 유클리드호제법을 이용한 풀이 

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

# 최대공약수
# a & b의 최대 공약수는 b & a를 b로 나눈 나머지의 최대 공약수
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

# 최소공배수 
# a와 b의 곱을 a와 b의 최대 공약수로 나눈 값
def lcm(a, b):
    return a * b // gcd(a, b)

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

 

#2 내장함수를 이용한 풀이

import math

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

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

 

---

 

유클리드호제 ?

유클리드 호제법은 최대공약수를 구하는 알고리즘이다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단 a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

# 128과 72의 최대공약수를 유클리드 호제법으로 구하기 :

1. 128(a) % 72(b) == 56(r) 

2. 72(b) % 56(r) == 16(r')

3. 56(r) % 16(r') == 8(r")

4. 16(r') % 8(r") == 0

8이 최대 공약수

 

# 파이썬 코드로 :

def gcd(a,b):
  if a%b==0:
    return b
  return gcd(b, a%b)

print(gcd(128,72))