HCFまたはGCDを見つけるPythonプログラム

2つの数値の最大公約数（HCF）または最大公約数（GCD）は、指定された2つの数値を完全に分割する最大の正の整数です。 たとえば、12と14のHCFは2です。

ソースコード：ループの使用

# Python program to find H.C.F of two numbers

# define a function
def compute_hcf(x, y):

# choose the smaller number
    if x > y:
        smaller = y
    else:
        smaller = x
    for i in range(1, smaller+1):
        if((x % i == 0) and (y % i == 0)):
            hcf = i 
    return hcf

num1 = 54 
num2 = 24

print("The H.C.F. is", compute_hcf(num1, num2))

出力

The H.C.F. is 6

ここでは、変数に格納されている2つの整数 num1 そして num2 に渡されます compute_hcf() 関数。 この関数は、これら2つの数値のHCFを計算し、それを返します。

関数では、HCFは最小の数値以下しかできないため、最初に2つの数値のうち小さい方を決定します。 次に、 for 1からその番号に移動するループ。

各反復で、数値が両方の入力数値を完全に分割するかどうかを確認します。 その場合、数値をHCFとして格納します。ループが完了すると、両方の数値を完全に分割する最大の数値になります。

上記の方法は理解と実装が簡単ですが、効率的ではありません。 HCFを見つけるためのはるかに効率的な方法は、ユークリッドアルゴリズムです。

ユークリッドアルゴリズム

このアルゴリズムは、2つの数値のHCFがそれらの差も分割するという事実に基づいています。

このアルゴリズムでは、大きい方を小さい方で割り、余りを取ります。 ここで、小さい方をこの余りで割ります。 余りが0になるまで繰り返します。

たとえば、54と24のHCFを求めたい場合、54を24で割ります。余りは6です。ここで、24を6で割り、余りは0です。したがって、6が必要なHCFです。

ソースコード：ユークリッドアルゴリズムの使用

# Function to find HCF the Using Euclidian algorithm
def compute_hcf(x, y):
   while(y):
       x, y = y, x % y
   return x

hcf = compute_hcf(300, 400)
print("The HCF is", hcf)

ここでは、 y ゼロになります。 声明 x, y = y, x % y Pythonで値の交換を行います。 Pythonでの変数の交換の詳細については、ここをクリックしてください。

各反復で、の値を配置します y に バツ そして残りは (x % y) に y、同時に。 いつ y ゼロになると、HCFが バツ。