Python GCD – GCD 또는 HCF를 찾는 4가지 방법

이 포스팅에서는 프로그램 예제를 사용하여 Python에서 GCD를 찾는 4가지 방법을 보여 드리겠습니다.

GCD는 HCF(최고 공통 인자)라고도 합니다. 그럼 우리가 어떻게 할 것인지 살펴보겠습니다.

방법 1: 루프 사용

n1 = 48

n2 = 36

 

#find smaller

if(n1>n2):

  smaller = n2

else:

  smaller = n1

  

#getting hcf  

i = 1

while(i<=smaller):

  if(n1%i==0 and n2%i ==0):

    hcf = i

  i  = i+1

 

print("hcf = ", hcf)

산출:
hcf = 12

따라서 이 프로그램에서는 먼저 n1과 n2에 값을 할당한 다음 두 숫자에서 더 작은 숫자를 찾습니다. 그런 다음 1에서 더 작은 숫자로 루프를 시작하여 숫자 n1과 n2로 완전히 나누어질 수 있는 숫자를 찾고 hcf라는 새 변수에 저장합니다. 루프가 끝나면 숫자 n1과 n2를 모두 완전히 나눌 수 있는 hcf 변수에 저장된 가장 높은 숫자를 얻게 됩니다. 가장 높은 숫자가 hcf가 됩니다 .

방법 2: 재귀 사용

def find_hcf(n1,n2):

    if(n2==0):

        return n1

    else:

        return find_hcf(n2,n1%n2)

 

n1 = 48

n2 = 36

 

hcf = find_hcf(n1,n2)

print ("highest common factor = ", hcf)

산출:
최고공약수 = 12

따라서 여기에 두 개의 인수를 받고 두 인수 사이의 가장 높은 공통 인수를 반환하는 재귀 함수가 있습니다.

방법 3: math.gcd() 사용

import math

 

n1 = 48

n2 = 36

 

hcf = math.gcd(n1,n2)

print("Highest Common Factor = ", hcf)

산출:
최고 공통 인수 = 12

Python에는 GCD를 알아내는 방법이 내장되어 있습니다. GCD를 찾기 위해 코딩하는 방법을 생각할 필요조차 없습니다. 우리가 해야 할 일은 math.gcd() 메소드를 사용하는 것뿐입니다. 그러면 GCD가 반환됩니다.

방법 4: 유클리드 알고리즘 사용

유클리드 알고리즘은 두 숫자의 최대 공약수(GCD)를 계산하는 효율적인 방법입니다. 다음은 유클리드 알고리즘을 사용하여 GCD를 찾는 방법을 보여주는 의사코드입니다.

유사 코드:

함수 gcd(a, b)

    b ≠ 0 인 동안

에조익
       t := b;

       b := a 모드 b;

       a := t;

    반환하다 ;

프로그램:

#implementing Euclidean algo

def get_gcd (x, y):

 

   while(y):

       x, y = y, x % y

 

   return x

 

n1 = 48

n2 = 36

 

hcf = get_gcd(n1,n2)

print("Highest Common Factor = ", hcf)

산출:

최고 공통 인수 = 12

이 프로그램에서는 유클리드 알고리즘을 구현하기 위해 get_gcd(int, int) 함수를 사용합니다. 유클리드 알고리즘에 대한 자세한 내용을 보려면   https://en.wikipedia.org/wiki/Euclidean_algorithm을 방문하세요.

Euclidean algorithm - Wikipedia