Maison > Article > développement back-end > Comment trouver le plus grand diviseur commun et le plus petit commun multiple en Python
Comment trouver le plus grand diviseur commun et le plus petit commun multiple en python
Trouver le plus grand diviseur commun
L'algorithme pour trouver le plus grand diviseur commun à l'aide de la division euclidienne est le suivant :
Pour deux entiers positifs a et b (a>b), leur plus grand diviseur commun est égal au reste de a divisé par b entre c et b Plus grand diviseur commun. Par exemple, si 10 et 25 sont divisés par 25, le quotient de 2 est 5, alors le plus grand commun diviseur de 10 et 25 est égal au plus grand commun diviseur de 10 et 5.
Le code spécifique est le suivant :
def gongyue(a, b): """ 欧几里得算法----辗转相除法 :param a: 第一个数 :param b: 第二个数 :return: 最大公约数 """ # 如果最终余数为0 公约数就计算出来了 while(b!=0): temp = a % b a = b b = temp return a
2. Trouver le plus petit commun multiple
Après avoir trouvé le plus grand commun diviseur d'un. et b, utilisez gongbei (a,b) = (a*b)/gongyue(a,b) Calculez le plus petit commun multiple de deux nombres :
# 求两个数的最小公倍数 def gongbei(a,b): return a * b / gongyue(a, b)
Apprentissage recommandé : Tutoriel vidéo Python
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!