Python Facteur commun le plus élevé (HCF / GCD)
Calculez le plus grand facteur commun (HCF) ou le plus grand diviseur commun (PGCD) de deux nombres à l'aide de l'algorithme euclidien.
Aperçu
Le plus grand facteur commun (HCF), également connu sous le nom de plus grand diviseur commun (PGCD), est le plus grand entier positif qui divise deux entiers ou plus sans laisser de reste.
L'algorithme euclidien est une méthode extrêmement efficace pour calculer HCF. Il indique que le PGCD de deux nombres divise également leur différence.
En Python, nous implémentons cela de manière itérative en utilisant une boucle while où nous remplaçons continuellement le plus grand nombre par le reste de leur division.
Sortie de code et d'exécution
Implémentation d'une boucle euclidienne pour trouver HCF/PGCD de deux nombres.
def find_gcd(a, b):
# Euclidean Algorithm
while b != 0:
a, b = b, a % b
return a
print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))GCD of 36 and 60 is: 12
GCD of 17 and 5 is: 1Mise en œuvre étape par étape
- Simplification des fractions et moteurs mathématiques
- Algorithmes de cryptographie (comme la génération de clés privées RSA)
- Concevoir des calendriers d'événements périodiques
Foire aux questions
Python a-t-il une fonction GCD intégrée ?
Oui ! La bibliothèque standard de Python contient « math.gcd(a, b) » qui utilise une implémentation C compilée sous le capot.
Sujets connexes
Trouvez le plus petit commun multiple (LCM) de deux nombres en utilisant leur relation HCF en Python.
Script de calculatrice simple PythonCréez une calculatrice de base en Python. Apprenez à mapper des opérateurs mathématiques, à prendre en compte les flux d'exécution des utilisateurs et à gérer la logique de manière native.