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

angryTom
angryTomoriginal
2020-02-13 09:39:0122807parcourir

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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn