| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2474 人关注过本帖
标题:求最小公约数
只看楼主 加入收藏
wanghaomin
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2010-11-18
结帖率:66.67%
收藏
已结贴  问题点数:20 回复次数:19 
求最小公约数
写一个函数,分别求俩个整数的最小公约数!
搜索更多相关主题的帖子: 公约数 
2011-01-03 19:40
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:2 
int gcd(int a, int b)
{
    int t;
    while (b)
    {
        a %= b;
        t = a, a = b, b = t;
    }
    return a;
}

是最大公约数

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2011-01-03 19:43
zhaoya881010
Rank: 9Rank: 9Rank: 9
来 自:芒砀古郡
等 级:蜘蛛侠
威 望:1
帖 子:339
专家分:1177
注 册:2010-11-21
收藏
得分:2 
程序代码:
#include<stdio.h>
void main()
{
    int gys(int,int);
    int gbs(int,int);
    int num1,num2,Gys,Gbs;          //Gys是最大公约数,Gbs是最小公倍数。
    printf("请你输入两个数:");
    scanf("%d,%d",&num1,&num2);
    Gys=gys(num1,num2);
    Gbs=gbs(num1,num2);
    if(Gys==1)
        printf("没有最大公约数\n");
    else
        printf("两个数的最大公约数是%d\n",Gys);
    printf("两个数的最小公倍数是%d\n",Gbs);
}
int gbs(int num1,int num2)//求两个数的最小公倍数。
{   int gys(int,int);
int Gbs,ys;
ys=gys(num1,num2);
Gbs=num1*num2/ys;
return(Gbs);
}

int gys(int num1,int num2)//求两个数的最大公约数。
{
    int t,ys=1;//ys是余数,t是中间变量。
    int i=2;
    if(num1<num2)
    {
        t=num1;
        num1=num2;
        num2=t;
    }
    if(num1%num2==0)return num2;
    else
    {
        while(1)
        {
            if((num1%i==0) && (num2%i == 0))
            {
                ys*=i;
                num1=num1/i;
                num2=num2/i;
            }
            if(i==num2)
                return ys;
            i++;
        }
    }
}

完整的最小公倍数也有的 参考下吧

Go Go Go
2011-01-03 19:52
qq1023569223
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:湖南科技大学
等 级:贵宾
威 望:26
帖 子:2753
专家分:13404
注 册:2010-12-22
收藏
得分:2 
最小公约数当然是1了
最大的话是:
int qq(int a,int b)
{
  int i,j,k;
  k=a<b?a:b;
  for(i=1;i<=k;i++)
     if(a%i==0&&b%i==0) j=i;
  return j;
}哪有楼上的那么长啊???

   唯实惟新 至诚致志
2011-01-03 19:53
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:2 
#include <stdio.h>

#define M 15
#define N 9

int gcd(int a, int b);

int main(void)
{

    int ret = gcd(M, N);

    printf("%d\n", ret);

    getchar();

    return 0;
}


int gcd(int a, int b)
{
    if (a == 0)
    {
        return b;
    }
    if (b == 0)
    {
        return a;
    }

    return gcd(b, a % b);
}

我就是真命天子,顺我者生,逆我者死!
2011-01-03 19:58
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
这个算法的原理是: 两个整数x 和y (x>y)的最大公约数 与 y和x%y 的最大公约相同。

我就是真命天子,顺我者生,逆我者死!
2011-01-03 20:02
wanghaomin
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2010-11-18
收藏
得分:0 
回复 楼主 wanghaomin
我要最小公约数了!谢谢!
2011-01-03 20:06
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
以下是引用qq1023569223在2011-1-3 19:53:24的发言:

最小公约数当然是1了
最大的话是:
int qq(int a,int b)
{
  int i,j,k;
  k=a
这个方法是最容易理解的,/  我推荐这方法 ~~~


我就是真命天子,顺我者生,逆我者死!
2011-01-03 20:08
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
以下是引用wanghaomin在2011-1-3 20:06:39的发言:

我要最小公约数了!谢谢!
大哥,我每天看帖回帖无数,却从没见过要求 解最小公约数的。/

我就是真命天子,顺我者生,逆我者死!
2011-01-03 20:09
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:2 
回复 7楼 wanghaomin
function lcd(int m, int n) { return 1; }

专心编程………
飞燕算法初级群:3996098
我的Blog
2011-01-03 20:12
快速回复:求最小公约数
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024696 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved