C语言最大公约数的三种方法.docx
92 浏览量
2023-11-22
23:02:07
上传
评论
收藏 18KB DOCX 举报
1.穷举法
输入 a,b 两个数字，比如 a>b,就从 2 到 b，挨个试，如果是公约数就
赋值给 k,因为是从小到大的穷举数字，所以最后赋值给 k 的数字一定是
最大的公约数。
#include<stdio.h>
int main ()
{
int a,b,c,i,k;
scanf("%d %d",&a,&b);
c=a>b?b:a;
for(i=2;i<=c;i++)
{
if(a%i==0&&b%i==0)
k=i;
}
printf("%d",k);
return 0;
}
2.辗转相除法
辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算
法。
用较大数除以较小数，再用出现的余数去除除数，再用出现的余数（第
二余数）去除第一余数，如此反复，直到最后余数是 0 为止。最后为
0，则除数为最大公约数。
比如求 18 与 30 的最大公约数
资源评论
