Posted on 2011-09-16 18:35
hoshelly 閱讀(1106)
評論(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