天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

计算两个正整数的最大公约数*

Posted on 2011-09-16 18:35 hoshelly 阅读(1068) 评论(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 



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理