Posted on 2011-09-16 18:35
hoshelly 阅读(1067)
评论(0) 编辑 收藏 引用 所属分类:
C
算法分析:因为对于a与b两个数,当a>b时,如果a中含有与b相同的公约数,则a-b也含有与b相同的公约数,反复循环,直到a和b相等为止,这时a或b就是它们的最大公约数。
1 #include<stdio.h>
2 int Maxcommonfactor(int a,int b);
3 void main()
4 {
5 int a,b,c;
6 printf("input two integer number:");
7 scanf("%d%d",&a,&b);
8 c=Maxcommonfactor(a,b);
9 if(c!=-1)
10 printf("The biggest common factor of %d and %d is %d\n",a,b,c);
11 else
12 printf("The biggest common factor of %d and %d isn't exist\n",a,b);
13 }
14 int Maxcommonfactor(int a,int b)
15 {
16 if(a<=0||b<=0)
17 return(-1);
18 while(a!=b)
19 {
20 if(a>b)
21 a=a-b;
22 else if(b>a)
23 b=b-a;
24 }
25 return(a);//返回的值为最大公约数
26 }
27
28