Jay Two's Blog (Korean Blog)

• 유클리드 호제법은 두 자연수의 최대공약수(GCD)를 효율적으로 구하는 알고리즘입니다.

• 이 방법은 큰 수를 작은 수로 나누어 나머지를 구하고, 이 과정을 나머지가 0이 될 때까지 반복합니다.

• 나머지가 0이 되는 순간의 나누는 수가 두 수의 최대공약수가 됩니다.

1. 두 수 중 큰 수를 작은 수로 나누어 나머지를 구합니다.
2. 이전 단계에서 작은 수를 이번 단계의 나머지로 대체하고, 나머지가 0이 될 때까지 이 과정을 반복합니다.
3. 나머지가 0이 되면, 그때의 작은 수가 최대공약수입니다.

• 1071과 1029의 최대공약수를 구해보겠습니다.

Step 1. 1071 % 1029 = 42
Step 2. 1029 % 42 = 21
Step 3. 42 % 21 = 0

• 따라서, 1071과 1029의 최대공약수는 21입니다.

python

def gcd(m, n):
    while n != 0:
        t = m % n
        m = n
        n = t
    return abs(m)

# 예제 사용
num1 = 1071
num2 = 1029
print(f"{num1}와 {num2}의 최대공약수는 {gcd(num1, num2)}입니다.")

• 이 코드는 두 수의 최대공약수를 계산하여 출력합니다.

• 위키피디아