PYTHON_알고리즘_GCD,LCD

두 수의 최대 공약수나 최소 공배수를 구할 때, 유클리드 호제법을 사용하면 쉽게 얻을 수 있다.

a = 10 b = 12일때 (예시)
x % y == r 꼴로 진행
10 % 12 == 10
12 % 10 == 2
10 % <2> == 0
==> 2가 최소 공배수

위와 같이, x와 y가 있고 먼저 x를 y로 나눴을 때 나머지를 r로 두었을 때 r이 0이 아니라면, x는 y가 되고 y는 r로 두고 다시 똑같이 진행한다.
이를 코드로 풀면 아래와 같다.

a,b = 10,12

while a % b !=0:
    r = a%b
    print(a,b,r)
    a,b = b,a%b
    
print(b)

위의 코드를 실행하면 아래와 같이 출력된다.

10 12 10
12 10 2
2

이를 통해서 최소 공약수를 구할수 있고 최대 공배수는 두 수를 곱하고 최소 공배수를 나누면 구할 수 있다.
이를 정리하자면 아래와 같이 정리할 수 있다.

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

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