简单问题的算法

求两个正整数的最小公约数越简单越好写错了应该是最大...

2025-03-28 05:28:49

推荐回答（5个）

回答（1）：

整数的最小公约数为1
main()
{
int p,r,n,m,temp;
printf("Please enter 2 numbers n,m:");
scanf("%d,%d",&n,&m);//输入两个正整数.
if(n{temp=n;
n=m;
m=temp;
}
p=n*m;//P是原来两个数n,m的乘积.
while(m!=0)//求两个数n,m的最大公约数.
{
r=n%m;
n=m;
m=r;
}
printf("Its MAXGongYueShu:%d\n",n);//打印最大公约数.
printf("Its MINGongBeiShu:%d\n",p/n);打印最小公倍数.
基本原理如下：
用欧几里德算法（辗转相除法）求两个数的最大公约数的步骤如下：
先用小的一个数除大的一个数，得第一个余数；
再用第一个余数除小的一个数，得第二个余数；
又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。
例如求1515和600的最大公约数，
第一次：用600除1515，商2余315；
第二次：用315除600，商1余285；
第三次：用285除315，商1余30；
第四次：用30除285，商9余15；
第五次：用15除30，商2余0。
1515和600的最大公约数是15。

两个正整数的最小公倍数=两个数的乘积÷两个数的最大公约数
由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。这就是说，求两个数的最小公倍数，可以先求出两个数的最大公约数，再用这两个数的最大公约数去除这两个数的积，所得的商就是两个数的最小公倍数。
例求105和42的最小公倍数。
因为105和42的最大公约数是21，
105和42的积是4410，4410÷21＝210，
所以，105和42的最小公倍数是210。

回答（2）：

求最大公约数的两种算法
________________________________________

辗转相除法和移位相减法（Euclid & stein 算法）
给出Stein算法如下：
1. 如果A=0，B是最大公约数，算法结束
2. 如果B=0，A是最大公约数，算法结束
3. 设置A1 = A、B1=B和C1 = 1
4. 如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)
5. 如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很显然啦，2不是奇数的约数)
6. 如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很显然啦，2不是奇数的约数)
7. 如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn
8. n++，转4
//greatest common divisor
//by heaton
//2005/03/11
#include
using namespace std;
//交换a ，b的值
void swap(int& a1,int &b1)
{
int temp;
temp=a1;
a1=b1;
b1=temp;
}

//辗转相除法
int gcd(int a,int b)
{
if(a < b)swap(a,b);
int c=a%b;
//cout<<"辗转相除法\n"<<"a b\n"< while(c!=0)
{
a=b;
b=c;
cout< c=a%b;
}
return b;
}
//移位相减法
int gcd2(int a,int b)
{
if(a < b)swap(a,b);
//cout< if(a==0)return b;
if(b==0)return a;
while(a != b)
{

if(( (a&1) == 0 ) && ( (b&1) == 0 )){
return 2*gcd2(a/2,b/2); //a,b are even numbers
}else if(( (a&1) == 1 ) && ( (b&1) == 0)){
return gcd2(a,b/2); //a is odd number , b is even number
}else if(((a&1) == 0 ) && ( (b&1) == 1) ){
return gcd2(a/2,b);//a....even ;b ...odd ...
}else if(((a&1) == 1 ) && ((b&1) == 1)){
return gcd2(b,(a-b)); //a,b are odd numbers
}
}
return b;
}
//通过递归调用求n个数的最大公约数
int ngcd(int a[],int n)
{

if (n==1)
return a[0];
else
return gcd2(a[n-1],ngcd(a,n-1));
}

int main()
{
int m=gcd(15,25);
cout<int n=gcd2(15,20);
cout<int a[]={450,90,15,45};//应该先按升序对数组排序
int x=ngcd(a,4);
cout<<" value:"<return 0;
}

回答（3）：

终于有人说要追求简单的了！
对你题目说要求最小公约数，不用函数，直接返回1就行了，任意两个正整数的最小公约数都是1~~~~
如果要求最大公约数，程序如下：
int gcd(int m,int n)
{
int t;
while(t=m%n)
{
m=n;
n=t;
}
return n;
}

回答（4）：

任何整数的最小公约数都是1了，是求最大公约数吧。

回答（5）：

看完水晶后真是想笑... 最小公约数!

最新问答

曲靖公司注册：创业需知，合伙开公司需要注意的事项

床上用品磨毛珊瑚绒法兰绒天鹅绒有什么区别，哪一种比较好，睡的舒服

WiFi下微博无法加载图片，但是4g可以，怎么办？

最幸运的选择荣威RX5，我们家的第一辆小汽车，生活有你更幸福

向加什么偏旁组成新字

信永中和会计师事务所（特殊普通合伙）广州分所怎么样？