Python에서 GCD 작업 구현

두 값의 최대공약수(HCF)라고도 하는 최대공약수(GCD)는 주어진 두 수를 나누는 가장 큰 수입니다. 최대공약수는 파이썬에서도 계산하고 구현할 수 있습니다.

이 자습서는 Python에서 최대 공약수에 대한 코드를 구현하는 다양한 방법을 보여줍니다.

재귀를 사용하여 Python에서 GCD용 코드 구현

함수 정의 블록에서 자신을 호출하는 함수를 재귀라고 합니다. 재귀를 사용하여 두 숫자의 GCD를 계산하는 함수를 만들 수 있습니다. 이 프로세스는 코드의 길이를 줄이는 데 매우 유용하며 불필요한 함수 호출을 최소화하는 데 유용합니다.

다음 코드는 재귀를 사용하여 Python에서 최대 공약수에 대한 코드를 구현합니다.

def gcd1(x, y):
    if y == 0:
        return x
    else:
        return gcd1(y, x % y)


x = 72
b = 60

print("The gcd is : ", end="")
print(gcd1(72, 60))

위의 프로그램은 다음과 같은 결과를 제공합니다.

출력:

The gcd is : 12

for 루프를 사용하여 Python에서 최대 공약수에 대한 코드 구현

간단한 for 루프와 if-else 문은 이 기사의 다른 방법과 동일한 작업을 수행하는 데 도움이 될 수 있습니다.

다음 코드는 for 루프를 사용하여 Python에서 최대 공약수에 대한 코드를 구현합니다.

def gcd2(a, b):

    if a > b:
        small = b
    else:
        small = a
    for i in range(1, small + 1):
        if (a % i == 0) and (b % i == 0):
            gcd = i

    return gcd


a = 72
b = 60

print("The gcd is : ", end="")
print(gcd2(72, 60))

위의 코드는 다음과 같은 결과를 제공합니다.

출력:

The gcd is : 12

유클리드 알고리즘을 사용하여 Python에서 최대 공약수 코드 구현

유클리드 알고리즘은 두 숫자의 최대 공약수를 빠르게 계산할 수 있는 또 다른 기술입니다.

유클리드 알고리즘은 두 가지 주요 사실로 정의됩니다.

• 작은 수에서 큰 수를 빼도 GCD에는 변화가 없습니다. 따라서 우리는 결국 두 숫자 중 더 큰 값을 계속 빼면서 GCD를 찾습니다.
• 여기서 빼는 대신 작은 수를 나누면 나머지 0이 발생할 때 알고리즘이 자동으로 중지됩니다.

아래의 다음 프로그램은 유클리드 알고리즘을 사용하여 파이썬에서 최대공약수에 대한 코드를 구현합니다.

def gcd3(p, q):

    while q:
        p, q = q, p % q

    return p


p = 72
q = 60

print("The gcd is : ", end="")
print(gcd3(72, 60))

코드는 다음 결과를 제공합니다.

출력:

The gcd is : 12

math.gcd() 함수를 사용하여 Python에서 최대 공약수 계산

이제 사용자 정의 함수를 만드는 대신 미리 정의된 math.gcd() 함수를 사용하여 두 숫자의 GCD를 계산할 수 있습니다. math 모듈은 gcd() 함수를 사용하기 위해 Python 코드로 가져와야 합니다.

다음 코드는 math.gcd() 함수를 사용하여 Python에서 최대 공약수를 계산합니다.

import math

a = math.gcd(72, 60)
print(a)

위의 프로그램은 다음과 같은 결과를 제공합니다.

출력:

12

Python 3.5 이상에서 gcd 함수는 math 모듈에 포함되어 있습니다. 이전 Python 버전에서 gcd 함수는 fractions 모듈에 포함되었습니다. 그러나 Python 3.5부터 더 이상 사용되지 않습니다.