Programme Python pour trouver le PGCD (PGCM) ou le PGCF (PGCD)

Python example in full

Dans cet exemple, vous allez apprendre à trouver le PGCD de deux nombres en utilisant deux méthodes différentes : la fonction et la boucle ainsi que l'algorithme d'Euclide

Pour comprendre cet exemple, vous devriez comprendre ce qui suitProgrammation PythonThème :

• Fonction Python

• Recursion Python

• Paramètres de la fonction Python

Le plus grand commun diviseur (PGCD) ou le plus grand commun facteur (PGCF) des deux nombres est le plus grand entier positif qui peut diviser parfaitement les deux nombres donnés. Par exemple, le PGCD(12, 14) est égal à2。

Code source : utilisation de la boucle

# Programme Python pour trouver le PPCM de deux nombres
# Définir une fonction
def compute_hcf(x, y):
# Choisir le nombre le plus petit
　　　　si x > y :
　　　　　　　　plus petit = y
　　　　sinon :
　　　　　　　　plus petit = x
　　　　pour i dans range(1, plus petit+1) :
　　　　　　　　si ((x % i == 0) et (y % i == 0)):
　　　　　　　　　　　　hcf = i　
　　　　return hcf
num1　=　54　
num2　=　24
print("H.C.F. is", compute_hcf(num1, num2))

Output result

H.C.F. is　6

Here, stored in the variable num1and num2two integers are passed to the compute hcf() function. The function calculates the H.C.F. of these two numbers and returns it.

In this function, we first determine the smaller of the two numbers F can only be less than or equal to the smallest number. Then we use a for loop from1to that number.

In each iteration, we check if our numbers perfectly divide the two input numbers. If so, we store this number as H.C.F., and at the end of the loop, we get the largest number that perfectly divides the two numbers.

The above method is easy to understand and implement, but it is not efficient. A more efficient way to find the HCF is the Euclidean algorithm.

Euclidean algorithm

This algorithm is based on the fact that the HCF of two numbers will also divide their difference.

In this algorithm, we divide the larger by the smaller, then take the remainder. Now, divide the smaller by this remainder. Repeat until the remainder is 0.

For example, if we want to find54and24hcf, we use54divided by24。The remainder is6。24divided by6，remainder is 0. Therefore,6is necessary hcf

Source code: Using Euclidean algorithm

# Function to find HCF using Euclidean 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)

Here we loop until y becomes zero. The statement x, y = y, x % y swaps the values in Python. Click here to learn more aboutSwapping variables in PythonMore information.

In each iteration, we place the value of y in x, and the rest (x % y) in y. When y becomes 0, we get the hcf of x.

Python example in full