Login dark

math/求最大公约数.md

辗转相除法

计算公式gcd(a,b) = gcd(b,a mod b)

代码

python

def gcd(a, b):
    while a != 0:
        a, b = b % a, a
 
    return b

php

function gcd($a,$b){
    while($a!=0){
        $tmp = $a;
        
        $a = $b % $a;
        $b = $tmp;
    }
    return $b;
}

echo gcd(104,40);

c

#include<stdio.h>
unsigned int Gcd(unsigned int M,unsigned int N)
{
    unsigned int Rem;
    while(N > 0)
    {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return M;
}
int main(void)
{
    int a,b;
    scanf("%d %d",&a,&b);
    printf("the greatest common factor of %d and %d is ",a,b);
    printf("%d\n",Gcd(a,b));
    return 0;
}