如何使用 Python 查詢 HCF 或 GCD？

在本文中，我們將向您展示如何在 Python 中查詢HCF（最大公因數）或GCD（最大公約數）。以下是完成此任務的各種方法

  • 使用 For 迴圈

  • 使用歐幾里得演算法

  • 使用 While 迴圈

  • 使用遞迴（樸素方法）

  • 處理 HCF 中的負數

什麼是 H.C.F. 或 G.C.D？

完美地整除兩個給定數字的最大正整數稱為最大公因數(H.C.F.)或最大公約數(G.C.D.)。

示例 - 12 和 14 的 HCF 為2。

使用 For 迴圈

演算法（步驟）

以下是執行所需任務應遵循的演算法/步驟 –

  • 建立一個變數來儲存輸入數字 1。

  • 建立另一個變數來儲存輸入數字 2。

  • 使用if 條件語句檢查第一個數字是否大於第二個數字。

  • 如果條件為真，則將第二個數字視為較小數字。

  • 否則將第一個數字視為較小數字。

  • 使用for 迴圈使用range()函式遍歷從 1 到小數字（range()函式返回一個從 0 開始並以 1（預設）遞增並在給定數字之前停止的數字序列）。

  • 使用if 條件語句檢查第一個和第二個數字是否都完全被索引 (i) 除以模運算子%（返回餘數），and運算子（如果兩個條件都為真則返回真）

  • 如果條件為真，則將相應的索引 (i) 值分配為 HCF

  • 列印輸入數字 1 和輸入數字 2 的結果 HCF。

示例

以下程式使用 for 迴圈返回輸入數字 1 和輸入數字 2 的 HCF –

# input number 1
inputNumber_1 = 30
# input number 2
inputNumber_2 = 14
# checking whether the first number is greater than
# the second one
if inputNumber_1 > inputNumber_2:
   # assigning the second number as a smaller number
   small_num = inputNumber_2
else:
   # else assigning the first number as a smaller number
   small_num = inputNumber_1
# traversing from 1 to the small number range
for i in range(1, small_num+1):
   # checking whether both the first and second numbers divide exactly by index (i)
   if((inputNumber_1 % i == 0) and (inputNumber_2 % i == 0)):
      # assigning the index(i) value as HCF if the condition is true
      resultHcf = i
# printing the HCF of input number 1 & input number 2
print("The H.C.F of", inputNumber_1, "and", inputNumber_2, "=", resultHcf)

輸出

執行上述程式後，將生成以下輸出 –

The H.C.F of 30 and 14 = 2

使用歐幾里得演算法

示例

以下程式使用歐幾里得演算法返回輸入數字 1 和輸入數字 2 的 HCF –

# creating a function that returns the HCF of two numbers passed to it
def calculateHcf(p, q):
   # traversing the loop until q times
   while(q):
      # assigning q value to p, p % q value to q
      p, q = q, p % q
   # returning p value(i.e, inputNumber_2)
   return p
# input number 1
inputNumber_1 = 15
# input number 2
inputNumber_2 = 4
# calling the calculateHcf() function by passing both the input numbers to it
resultHcf = calculateHcf(inputNumber_1, inputNumber_2)
# printing the HCF of input number 1 & input number 2
print("The H.C.F of", inputNumber_1, "and", inputNumber_2, "=",
calculateHcf(inputNumber_1, inputNumber_2))

輸出

執行上述程式後，將生成以下輸出 –

The H.C.F of 15 and 4 = 1

使用 While 迴圈（重複減法）

示例

以下程式使用 while 迴圈（重複減法方法）返回輸入數字 1 和輸入數字 2 的 HCF –

# input number 1
inputNumber_1 = 40
# input number 2
inputNumber_2 = 5
# storing both the numbers in temporary variables
# for not getting disturbed
temp_1 = inputNumber_1
temp_2 = inputNumber_2
# traversing the loop until both the numbers are not equal
while inputNumber_1 != inputNumber_2:
   # checking whether inputNumber_1 is greater than inputNumber_2
   if inputNumber_1 > inputNumber_2:
      # assigning inputNumber_1-inputNumber_2 value to inputNumber_1
      inputNumber_1 -= inputNumber_2
   else:
      # else assigning inputNumber_2-inputNumber_1 value to inputNumber_2
      inputNumber_2 -= inputNumber_1
# printing the HCF of input number 1 & input number 2
print("The H.C.F of", temp_1, "and", temp_2, "=", inputNumber_1)

輸出

執行上述程式後，將生成以下輸出 –

The H.C.F of 40 and 5 = 5

使用遞迴（樸素方法）

示例

以下程式使用遞迴返回輸入數字 1 和輸入數字 2 的 HCF –

# creating a function that returns the HCF of two numbers passed to it
def calculateHcf(num_1, num_2):
   # checking whether the second number is equal to 0
      if(num_2 == 0):
         # returning the absolute value of the first number if the condition is true
         return abs(num_1)
      else:
         # else returning the resultant HCF by calling the calculateHcf() function
         # by passing num_2, value of num_1 % num_2 as arguments
         return calculateHcf(num_2, num_1 % num_2)
# input number 1
inputNumber_1 = 32
# input number 2
inputNumber_2 = 6
# calling the calculateHcf() function by passing both the input numbers to it
print("The H.C.F of", inputNumber_1, "and", inputNumber_2, "=",
calculateHcf(inputNumber_1, inputNumber_2))

輸出

執行上述程式後，將生成以下輸出 –

The H.C.F of 32 and 6 = 2

處理 HCF 中的負數

兩個數字的 HCF 永遠不可能為負，因此，如果任何數字為負，只需將它們乘以 -1 使其變為正數。

在這種方法中，透過在歐幾里得演算法中有效地使用模運算子 (%)，提高了重複減法的複雜度。

以下程式透過處理 HCF 中的負數，使用 while 返回輸入數字 1 和輸入數字 2 的 HCF –

示例

# creating a function to calculate the hcf
def calculateHcf(x, y):
   return y == 0 and x or calculateHcf(y, x % y)
# input number 1
inputNumber_1 = -4
# input number 2
inputNumber_2 = 15
# If the user types a negative number, we simply change it to a positive number.
# HCF is the highest positive number that divides both numbers
# -4 & 15 --> HCF = 1 (as the highest number that divides both)
# -4 & -15 --> HCF = 1 (as the highest number that divides both)
inputNumber_1 >= 0 and inputNumber_1 or -inputNumber_1
inputNumber_2 >= 0 and inputNumber_2 or -inputNumber_2
# calling the calculateHcf() function by passing both the input numbers to it
print("The H.C.F of", inputNumber_1, "and", inputNumber_2, "=",
calculateHcf(inputNumber_1, inputNumber_2))

輸出

執行上述程式後，將生成以下輸出 –

The H.C.F of -4 and 15 = 1

結論

在本文中，我們學習瞭如何使用四種不同的方法在 Python 中查詢數字的 gcd/hcf。我們還學習了在計算 HCF 時如何處理負數。

更新於：2022 年 10 月 28 日

2K+ 瀏覽量

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.