선행지식

• 사칙연산

설명

유클리드의 호제법(Euclidean algorithm)은 두 수의 최대공약수를 구하는 알고리즘이다.

예를 들어, 24와 36의 최대공약수를 구하는 과정은 다음과 같다.

1. 36을 24로 나눈다.
2. 나머지가 12이므로, 24를 12로 나눈다.
3. 나머지가 0이므로, 12가 최대공약수이다.

이를 수식으로 표현하면 다음과 같다.

gcd(24, 36) = gcd(36 % 24, 24) = gcd(12, 24 % 12) = gcd(12, 0) = 12

파이썬으로 구현하면 다음과 같다.

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

위의 예제에서 gcd(24, 36)을 구하는 코드는 다음과 같다.

print(gcd(24, 36)) # Output: 12

두 수의 최소공배수(LCM)와 최대공약수(GCD)는 다음 관계가 성립한다: m × n = GCD × LCM.

따라서 GCD를 구한 후, 두 수의 곱을 GCD로 나누면 최소공배수를 얻을 수 있다.