[알고리즘] 최대공약수, 최소공배수 - 파이썬

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

큰 수를 작은 수로 나눈 나머지로 큰 수를 대체한다. 큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다. 나누어 떨어질 때(나머지가 0일 때), 나누는 수가 최대공약수이다.

 

def gcd(a,b):
    if b < a:
        a,b = b,a

    while b:
        n = a % b
        a, b = b, n
        
    return a

최소공배수 = 두 수의 곱 / 최대공약수

def lcm(a,b):
    return (a*b)//gcd(a,b)

https://wikidocs.net/21759

 

위키독스

https://blockdmask.tistory.com/53

[유클리드 알고리즘] GCD 최대공약수 (반복문, 재귀)

https://myjamong.tistory.com/138

최대공약수(GCD), 최소공배수(LCM) 구하기 유클리드 호제법 알고리즘 :: 코드자몽