|
1辗转相除法：输入两个正整数a,b(假设a>b),用大数除以小数得到余数为r,即用a除以b得到余数r,然后循环以下条件，（a=b;b=r;r=a%b）;直到r等于0时，结束循环，则b即为两个数的最大公约数。
??????? 2相减法：输入两个正整数作差，将差值赋给其中一个较大的整数，再将新得到的整数与原来较小的整数作差。循环上述步骤，直到两个数的差值为0，则得到的两个数值相等的数就为起始输入的两个数的最大公约数。
????? 3? 穷举法：判断输入的两个整数中较小的数能否被较大的数整除，如果能，则这个较小的数就是两数的最大公约数，否则，令较小的依次减1，逐一判断能否被两数整除，即可找到两数的最大公约数。
{
?? ?int a,b,r,result;
?? ?printf("请输入非0两个整数:\n");
?? ?scanf("%d%d",&a,&b);
??? while(a==0||b==0)? //判断输入的两个数不能为0
?? ?{
?? ??? ?printf("输入有误，请重新输入\n");
?? ??? ?scanf("%d%d",&a,&b);
?? ?}
?? ?if(a>=b)
?? ??? ? r=a%b;??????? //较大的整数除以较小的整数取余数
?? ?else
?? ?{
?? ??? ? r=a;????????? //如果a小于b,交换a,b的值
?? ??? ? a=b;
?? ??? ? b=r;
? r=a%b;
?? ?} ?
??? while(r!=0)??????? //当余数不为0时，继续辗转相除，用较大的整数除以较小的整数取余数
?? ?{???????????????? ?
?? ??? ?a=b;
?? ??? ?b=r;
?? ??? ?r=a%b;???????? //因为r为余数，一定小于b
?? ?}
??? printf("两个数的最大公约数=%d\n",b);? //直到余数为0，输出a,b的最大公约数
?? ?printf("\n\n");
?? ?main();
}
?
int m,n;
?? ?printf("请输入两个非0整数:\n");
?? ?scanf("%d%d",&m,&n);
?? ?while(m==0||n==0)??? //判断输入的两个数不能为0
?? ?{
?? ??? ?printf("输入有误，请重新输入\n");
?? ??? ?scanf("%d%d",&m,&n);
?? ?}
?? ?while(m-n!=0)?????? //m与n反复作差，直到m与n的差值为0
?? ?{
?? ??? ?if(m<n)n=n-m;?? ?
?? ??? ?else m=m-n;
?? ?}
?? ?printf("两数的最大公约数=%d\n",m);
??? printf("\n\n");
?
{? ?
?? ?int c,d;
?? ?printf("请输入非0两个整数:\n");
?? ?scanf("%d%d",&c,&d);
?? ?while(c==0||d==0)???????? //判断输入的两个数不能为0
?? ?{
?? ??? ?printf("输入有误，请重新输入\n");
?? ??? ?scanf("%d%d",&c,&d);
?? ?}
?? ?int min = (c>d)?d:c;??????? //求两个数的较小者
??? while(min > 0)
??? {
??????? if(c%min == 0 && d%min == 0) break;//都能整除，则为最大公约数。
??????? min--;???????????????? //将两者中较小的数依次减1
??? }
??? printf("两数的最大公约数=%d\n",min);
?
|