求2个正整数最大公约数最小公倍数的方法？

估计方法比较多，想了半天，感觉找不到最佳方法！我是初学者，可能有很多还不知道，希望大家能给个比较好的思路。
  写了个程序如下（感觉比较复杂）

#include<stdio.h>
int main()
{//求两个正整数的最大公约数和最小公倍数
    void gbgy(int m,int n,int k);
    int m,n,max,min,k;
printf("请输入2个正整数\n");
scanf("%d%d",&m,&n);
if(m==n)
{
max=n;
min=n;
printf("最小公倍数是:%d,最大公约数是:%d\n",min,max);
}
else if(m>n)
{
if(m%n==0)
{
max=n;
min=m;
printf("最小公倍数是:%d,最大公约数是:%d\n",min,max);
}else {
k=n;
gbgy(m,n,k);
}
}
else
{
if(n%m==0)
{
max=m;
min=n;
printf("最小公倍数是:%d,最大公约数是:%d\n",min,max);
}else{
k=m;
gbgy(m,n,k);
}
}

return 0;
}
void gbgy(int m,int n,int k)
{//求最大公约，最小公倍函数
int max,min;
for(int i=1;i<=k;i++)
if(m%i==0&&n%i==0)
max=i;
min=m/max*(n/max)*max;//求出最小公倍数（最小公倍与最大公约的关系）
printf("最小公倍数是:%d,最大公约数是:%d\n",min,max);
}

14 个解决方案

#1

#include"stdio.h"
void main()
{
void num(int x,int y);
int X,Y;
printf("Input two numbers:");
scanf("%d,%d",&X,&Y);
num(X,Y);
}
void num(int x,int y)
{
int GCD,LCM,team;
GCD=LCM=x>y?x:y;
for (;LCM<=(x*y);LCM++)
     {
      if ((LCM%x==0)&&(LCM%y==0))
         {printf("Lease common multiple is %d\n",LCM);break;}
     }
for (;GCD>=1;GCD--)
     {
      if ((x%GCD==0)&&(y%GCD==0))
         {printf("Greatest common divisor is %d\n",GCD);break;}
     }
}

偶也是初学者，乱写的～

#2

// GCD的几个性质

// 1. 如果a,b都是偶数, 则gcd(a, b) = gcd(a/2, b/2)
// 2. 如果a是奇数, b是偶数, 则gcd(a, b) = gcd(a, b/2)
// 3. 如果a,b都是奇数, 则gcd(a, b) = gcd((a-b)/2, b)

unsigned binary_gcd(unsigned x, unsigned y)
{
    // 记录2的幂数

    unsigned k = 0;

    // 处理特殊的情况

    if(x == 0) return y;
    if(y == 0) return x;

    // xy都是偶数, 则根据性质1

    while(((x|y)&1) == 0)
    {
        x >>= 1; y >>= 1; k++;
    }

    // xy中只有一个是偶数, 根据性质2

    while((x&1) == 0) x >>= 1;

    // xy都是奇数, 根据性质3

    while(y)
    {
while((y&1) == 0) y >>= 1;

        unsigned t = y;
        y = (x>y)? x-y: y-x;
        x = t;
    }

// 根据性质1

    return (x<<k);
}

#3

可以找本数论方面的书看看

#4

unsigned gcd( unsigned a , unsigned b )
{
  if( !b )
    return a;
  while( a%=b )
    if( !( b%=a ) )
      return a;
  return b;
}
unsigned lcm( unsigned a , unsigned b )
{
   return !a||!b?0:a/gcd(a,b)*b;
}

#5

辗转相除，取余数，做乘法就可以得公约数

#6

最大公约数：辗转相除
最小公倍数：a*b/gcd(a, b)

#7

你们的算发我就不看了，字太小了，看了头晕
主要的分析我说下哈

最大公约数用展转相除法求得
最小公倍书，用两个数的积去除于最大工约数

#8

lz可以google下欧几里德算法。

==================================
欢迎访问我的个人主页：http://www.lingjie.net/
==================================

#9

给个简单一点的.
main()
{
　int a,b,num1,num2,temp;
　printf("please input two numbers:\n");
　scanf("%d,%d",&num1,&num2);
　if(num1 　{ temp=num1;
　　num1=num2;　
　　num2=temp;
　}
a=num1;b=num2;
while(b!=0)/*利用辗除法，直到b为0为止*/
　{
　　temp=a%b;
　　a=b;
　　b=temp;
　}
printf("gongyueshu:%d\n",a);
printf("gongbeishu:%d\n",num1*num2/a);
}

#10

不懂有没有写错,

#11

很多书上都有的!~

先查资料!~

自学能力很重要的!~

#12

很多书上都有的习题。

一般解法：

int main()
{
int a,b,num1,num2,temp;
printf("please input two numbers:\n");
scanf("%d,%d",&num1,&num2);
if(num1>num2)
{temp=num1;
num1=num2;
num2=temp;
}
a=num1;b=num2;
while(b!=0)
{
temp=a%b; /*利用辗除法，直到b为0为止*/
a=b;
b=temp;
}
printf("gongyueshu:%d\n",a);
printf("gongbeishu:%d\n",num1*num2/a);

return 0;
}

#13

//来个递归求最大公约数，其实也是辗转求余的，只是看起来简洁，不如递推效率高
int rgcd( int v1, int v2 )
{
if ( v2 != 0 )
return rgcd( v2, v1%v2 );
return v1;
}

#14

最大公约数(Euclid算法)--算法导论示例
http://blog.csdn.net/hedongfu/archive/2006/07/08/894170.aspx

#1

#2

#3