注册 登录
编程论坛 C++教室

最大公约数

欣飞飞 发布于 2013-10-07 17:35, 457 次点击
求两个正整数m和n的最大公约数
测试数据有多组,处理到文件尾。每组测试数据在同一行输入两个正整数m和n。
每组输出m和n的最大公约数。


 #include<iostream>  
#include<string>  
using namespace std;  
int main()  
{  
    int a,b,temp;  
    while(cin>>a>>b)  
    {  
        if(a<b)  
        {  
            temp=a;a=b;b=temp;     //这里是什么意思啊?能不能给我说我说明一下啊!!
        }  
            while((temp=a%b)!=0)    //这里为什么要用a%b啊,我不懂,求给位大神指教啊!!
            {  
                a=b;b=temp;  
            }  
         
        cout<<b<<endl;  
    }  
    return 0;  
}
6 回复
#2
y12074358812013-10-07 20:13
欧几里德算法,数论里面的内容,想研究它的原理找本数论的书来看
#3
qunxingw2013-10-07 20:16
最大公约数是个伟大经典的方法,值得反复研究,需要理解运算过程,再利用语言的表现形式实现。楼主的问题表现在语法基础还需补习。
#4
欣飞飞2013-10-08 16:02
我刚开始学编程,请各位大大多多照顾啊!!
#5
lesely2013-10-08 19:27
回复 楼主 欣飞飞
temp=a;a=b;b=temp;     //这里是什么意思啊?能不能给我说我说明一下啊!!
这个意思是比较大小,交换位置。
#6
穆宇杰2013-10-08 20:21
#7
小男孩的围裙2013-10-09 00:18
给你举几个例子吧。
输入3 10。
经过
if(a<b)  
   {  
      temp=a;a=b;b=temp;
    }
a肯定是大数,b相对应就是小数。(这个比吃饭还简单,不知道就没办法了)
然后就是10%3得1  
由于a=b;b=temp;
又得3%1得0。
输出b就为最大公约数1。

如果输入10 6,
10%6得4  6%4得2 4%2得0 输出b就为最大公约数2。
不知道为什么就是最大公约数的话就听二楼的去学习学习欧几里德算法。
1