#include<stdio.h>
unsigned int gcd(unsigned int M, unsigned int N)
{
int rem;
if(M < N)/*exchange value to=>M>N*/
{
int temp = M;
M = N;
N = temp;
}
while(N > 0)
{
rem = M % N;
M = N;
N = rem;
}
return M;
}
int main()
{
printf("%d\n", gcd(25, 45));
return 0;
}
这种算法通过不断的求余数,直到最后结果为0,倒数第二个数就是最大公因数。这个算法很高效,但是自己怎么能证明最后非0的那个余数就一定是正确答案昵,作为数学渣有点困扰。
(借张图)两个数都是由最大公约数堆出来的,所以相减、取模最大公约数肯定是不变的。(直观解释)
参见
辗转相除法。
Greatest Common Divisor。
手打公式太繁,改用拍照。