E12.【C语言】练习：求两个数的最大公约数
1.枚举
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
int a = 0;
int b = 0;
int tmp = 0;
scanf("%d %d", &a, &b);
if (a < b)
{
for (int i=1; i < a; i++)
{
if (0==a% i && 0==b%i)
tmp = i;
}
}
if (a>b)
{
for (int i = 1; i < b; i++)
{
if (0 == b % i && 0 == a % i)
tmp = i;
}
}
if (a = b)
tmp = a;
printf("%d", tmp);
return 0;
}
注意i不能从0开始否则有Integer division by zero报错，即整数除以零
但是代码可以进一步简化：
输入两个数-->找出最小数-->从最小数开始：从大向小找，一旦找到就是最大公约数
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
int a = 0;
int b = 0;
int tmp = 0;
scanf("%d %d", &a, &b);
if (a > b)
tmp = b;
else
tmp =a;
while (1)//一直循环
{
if (0 == a % tmp && 0 == b % tmp)
{
printf("%d", tmp);
break;
}
tmp--;
}
return 0;
}
2.辗转相除法
定义：先用较大的数除以较小的数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。此时的除数就是所求的最大公约数。
18%24=18-->24%18=6-->18%6=0-->6是最大公约数
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
int a = 0;
int b = 0;
int tmp = 0;
scanf("%d %d", &a, &b);
while (tmp=a%b)//循环,m%n=0退出
{
a = b;
b = tmp;
}
printf("%d", b);
return 0;
}
最小公倍数=a*b/最大公约数
Ongwu博客 版权声明：以上内容未经允许不得转载！授权事宜或对内容有异议或投诉，请联系站长，将尽快回复您，谢谢合作！