输入两个数，程序能求出它们最大公约数和最小公倍数！

新人问题！~
要求，输入两个数，程序能求出它们最大公约数和最小公倍数！

14 个解决方案

#1

//最大公约数和最小公倍数
#include <iostream>
using namespace std;

long lcm(long,long); //返回最小公倍数 
long gcd(long,long); //返回最大公约数

int main () 
{
    int m,n;
    cout << "Enter two positive integers: ";
    cin >> m >> n;
    cout << "gcd(" << m << "," << n << ") = " << gcd(m,n) <<endl;
    cout << "lcm(" << m << "," << n << ") = " << lcm(m,n) <<endl;
    
    cin.get();
    cin.get();
    return 0;
}

long gcd (long m,long n) 
{//计算最大公约数 
     if (m > n) swap(m,n);
     while(n > 0) {
             int r = m % n;
             m = n;
             n = r;
     }
     return m;
}

long lcm (long m,long n)
{//计算最小公倍数 
     return (m*n / gcd(m,n));
}

#2

/*  最大公约数的递归函数同时求最小公倍数 */
#include <stdio.h>

int maxFactor(int n, int m);

int main()
{
    printf("maxFactor(18,8) = %d\n",maxFactor(18,8));
    printf("minBeishu(18,8) = %d\n",minBeishu(18,8));
    system("pause");
}

int maxFactor(int n, int m)
{        
    
    if(n%m == 0)
        return m;
    else 
        return maxFactor(m, n%m); 
}

int minBeishu(int n, int m)
{
    return (n* (m / maxFactor(n,m)));
}

#3

#include <iostream>
using namespace std;

int main()
{
	int a,b,t1,t2;
	cin>>a;
	cin>>b;
	t1=b;
	t2=a;

	if(a>b) 
		{ 
			if(a%b==0) cout<<b<<"是"<<a<<"的最大公约数"<<endl;
			else
			{
				while(b>0)
				{
					t1--;
					if(a%t1==0&&b%t1==0) 
						{
							cout<<"a，b最大公约数为"<<t1<<endl; 
							break;

						}
				}
			}
		}
	if(a<b) 
		{ 
			if(b%a==0) cout<<a<<"是"<<b<<"的最大公约数"<<endl;
			else
			{
				while(b>0)
				{
					t2--;
					if(a%t2==0&&b%t2==0) 
						{
							cout<<"a，b最大公约数为"<<t2<<endl; 
							break;
						}
				}
			}
		}
	return 0;

}

好早编的找来贴上 呵呵
那个最小公倍数的思想跟这个差不多

#4

这个明白算法就OK了.
 

设这2个数分别为X,Y
如果X>Y;
欲求X和Y的最大公约数只要求Z=X-Y与Y的最大公约数即可,然后判断Z与Y的大小,假设Z>Y,再求Z-Y与Y的最大公约数,如此循环,运用递归就行,知道相等为止.相等的数即为最大公约数.


至于求最小公倍数,既然知道了最大公约数就只需要用X和Y的积除以最大公约数即可得到最小公倍数.

#5

#include <stdio.h>
int maxyu(int x,int y);
int minbe(int x,int y);
int main(int m,int n)
{
 int c;
 int d;
 printf("Put two numbers:\n");
 scanf("%d,%d",&m,&n); 
 c = maxyu(m,n);
 printf("最大公约数是：%d\n",c);
 d = minbe(m,n);
 printf("最小公倍数是：%d\n",d);
 return 0;
}
int minbe(int x,int y)//求最小公倍数
{
int t;
int p=1;
int min=1;
if (x<y)//将大数始终放在x里面
{
t = x;
x = y;
y = t;
}    
if(x%y==0)
{
min=x;
}
    else
for(int i=2;i<x/2;i++)//
{
if((x%i==0)&&(y%i==0))
{
               x=x/i;
   y=y/i;
   p=p*i;
}
if((x%i!=0)||(y%i!=0))
{
min = p*x*y;
}
}

return min;
}


int maxyu(int x,int y)//求最大公约数
{
int t;
int q=1;
int max=0;
if (x<y)
{
t = x;
x = y;
y = t;
}    
if(x%y==0)
{
max=y;
}
else
for(int i=2;i<x/2;i++)
{
if((x%i==0)&&(y%i==0))
{
x=x/i;
y=y/i;
q=i*q;
}
max = q;
}
return max;
}

#6

1L的是什么啊？？？？第2个……………………第1个..我晕

#7

顶2L的！！终于明白这个叫低归了....

#8

/************************************************
问题：任意输入两个数，求其最小公倍数和最大公约数。
徐晓春   2008-3-14  xxc168.cn

**************************************************/

#include <stdio.h>
void main()
{
	do
	{
	long gbs(long num1,long num2);
	long x,y;
     printf("问题：任意输入两个数，求其最小公倍数和最大公约数。\n\n\n");
	 printf("请输入两个整数，以空格相隔:");
	scanf("%d %d",&x,&y);
	gbs(x,y);
	printf("是否继续计算？输入y(Y)继续，其他任意键退出：");
	getchar();
	}
	while(getchar()=='y'||getchar()=='Y');
}

long gbs(long num1,long num2)
{
	int a;   //a为num1除num2取余
	long b,t;//b为num1与num2互换时的中间变量。t为num1*num2
   if(num1<num2)
	{
	   b=num1;
	   num1=num2;
	   num2=b;	//m与n互换。把大数放在m中，小数放在n中。
	}
   t=num1*num2; //将m*n放在t中，后面求最小公倍数时用。
	a=num1%num2;
    while(a!=0)  //for(;a!=0;)
	{
		num1=num2;
	    num2=a;
		a=num1%num2;
	}
	printf("这两个数的最大公约数是：%d\n这两个数的最小公倍数是：%d\n\n\n",num2,(t/num2));
}

#9

辗转相除

int gcd(int a, int b) 
{ return (a%b)?gcd(b,a%b):b; } 

int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    printf("最大公约数:%d; 最小公倍数:%d\n",gcd(a,b),a/gcd(a,b)*b);     
    return 0;
}

#10

好帖！

#11

#include<iostream>
using namespace std;

template <typename T>
T gcd(T x,T y);

template <typename T>
long double  minmul(T x,T y);

int main()
{ 
  int a,b;
  cout<<"Enter two numbers:( negative to quit)"<<endl;
  while( cin>>a>>b)
  {
       if(a<=0||b<=0)
         cout<<"Can not be negative!Enter again"<<endl;
      else 
         break;
  }
  cout<<gcd(a,b)<<" "<<minmul(a,b)<<endl;
  
  system("pause");
  return 0;
}

template <typename T>
T gcd(T x,T y)
{  
   if(x<y)
     return gcd(y,x);
   if(y==0)
     return x;
   else
     return gcd(x-y,y);//当数字比较大的时候 ，减法操作比除法操作快的多
}
template <typename T>
 long double minmul(T x,T y)
{
  return x/gcd(x,y)*y;
}

适合与比较大的数。

#12

#include<iostream>
using namespace std;

template <typename T>
T gcd(T x,T y);

template <typename T>
long double  minmul(T x,T y);

int main()
{ 
  int a,b;
  cout<<"Enter two numbers:( negative to quit)"<<endl;
  while( cin>>a>>b)
  {
       if(a<=0||b<=0)//刚才这里有个错误，已改正！
         cout<<"Can not be negative!Enter again"<<endl;
      else 
         break;
  }
  cout<<gcd(a,b)<<" "<<minmul(a,b)<<endl;
  
  system("pause");
  return 0;
}

template <typename T>
T gcd(T x,T y)
{  
   if(x<y)
     return gcd(y,x);
   if(y==0)
     return x;
   else
     return gcd(x-y,y);
}
template <typename T>
 long double minmul(T x,T y)
{
  return x/gcd(x,y)*y;
}

#13

if(a <=0||b <=0)//刚才这里有个错误，已改正！

#14

#include<stdio.h>
#include<string.h>
#define MAX 50
int gcd(int m,int n)
{
   if(m%n==0)return n;
   else return gcd(n,m%n);
}
int max(int a[],int b[],int number,int maxx)
{
 int i;
 for(i=0;i<number-1;i++)
   {
   b[i]=gcd(a[i],a[i+1]);
   a[i+1]=b[i];
   }
   maxx=b[i-1];
   return maxx;
}
int lcm(m,n)
{
 return m*n/gcd(m,n);
}
int min(int a[],int b[],int number,int minn)
{
 int i;
 for(i=0;i<number-1;i++)
 {
 b[i]=lcm(a[i],a[i+1]);
   a[i+1]=b[i];
   }
   minn=b[i-1];
   return minn;
}
main()
{
   int a[MAX],b[MAX],c[MAX];
   int number,i,maxx,minn;
   printf("Please input number:");
   scanf("%d",&number);
   printf("now please input %d number:",number);
   for(i=0;i<number;i++)
   scanf("%d",&a[i]);
   for(i=0;i<number;i++)
 c[i]=a[i];
   maxx=max(a,b,number,maxx);
   minn=min(c,b,number,minn);
   printf("The greatest common divisor is:%d\n",maxx);
   printf("The lowest common multiple is:%d\n",minn);
}
这是我写的程序，楼主可以参考一下