유클리드 호제법 - 최대공약수, 최소공배수

유클리드 호제법

• 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘
• 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

코드

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

 

math 모듈 gcd 을 사용할 수 있다.

from math import gcd

gcd(a, b)

 

최소공배수 구하기

L = (A * B) / G

 

코드

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

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