Python에서 GCD 작업 구현

Vaibhhav Khetarpal 2023년1월30일
  1. 재귀를 사용하여 Python에서 GCD용 코드 구현
  2. for 루프를 사용하여 Python에서 최대 공약수에 대한 코드 구현
  3. 유클리드 알고리즘을 사용하여 Python에서 최대 공약수 코드 구현
  4. math.gcd() 함수를 사용하여 Python에서 최대 공약수 계산
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부터 더 이상 사용되지 않습니다.

Vaibhhav Khetarpal avatar Vaibhhav Khetarpal avatar

Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.

LinkedIn

관련 문장 - Python Number