欧几里得算法
欧几里得算法基本思想: Gcd(a,b) = Gcd(b , a%b) 直到最后余数为0
例如 Gcd(70,15) = Gcd(15,10) 70%15 = 10
Gcd(15,10) = Gcd(10,5) 15%10 = 5
Gcd(10,5) = Gcd(5,0) 10%5 = 0 余数为0 计算结束，最后结果为 5
这里还有一些比较有意思的定理 如果 M > N, 则 M mod N < M/2
有兴趣的可以自己证明一下 提示分为两种情形 1 N <= M/2 2 N > M/2
#include<stdio.h> // 欧几里得算法
// 用于求两个整数的最大公因数int Gcd( int M,int N)
{
int Rem;
// 如果M < N 第一次运算将他们互换
while(N > 0) //当余数为0时循环终止
{
Rem = M % N;
M = N;
N = Rem;
}
return M;
}
{
printf("%d",Gcd(70,15));
return 0;
}
查看30道真题和解析
投递米哈游等公司8个岗位
