求最大公约数(欧几里得算法)

发表于

两个正整数a和b(a>b),a除以b的余数为c，那么a和b的最大公约数等于c和b的最大公约数，这就是欧几里得算法，又叫辗转相除法

45和6的余数是3，6和3的余数为0，那么最大公约数就是3,用代码表示如下:

1
2
3
4
5
6
7
8
int a = 45;
int b = 6;
while(b!=0){
    int temp = a%b;
    a = b;
    b = temp;
}
print("%d",b);

1.如果b等于0，计算结束，a就是最大公约数
2.如果b不等于0，那么a除以b的余数为temp，让a等于b，b等于余数temp
3.回到第一步