现在的位置: 首页 > 综合 > 正文

数论基础之辗转相除法求最大公约数

2018年04月29日 ⁄ 综合 ⁄ 共 480字 ⁄ 字号 评论关闭

    求两个正整数m,n的最大公约数算法

【分析】:求两个正整数的最大公约数可以采用 辗转相除 的算法,分别用m,n,r表示被除数,除数,和余数。

                (1) 求m除以n得到的余数r。

                (2)判断 r == 0,算法结束,则n为两个数的最大公约数。

                                 r!=0,则把n赋值给m,r赋值给n,在做m除以n

                (3) 转到第二步继续进行。。。。直到 r == 0 为止,输出n的大小。

# include<cstdio>
# include<iostream>

using namespace std;

int main(void)
{
    int m,n;
    cin>>m>>n;
    int  r = m%n;
    while ( r != 0 )
    {
        m = n;
        n = r;
        r = m%n;
    }
    cout<<n<<endl;


    return 0;
}

如果题目中要求我们求解 最小公倍数,那么我们只要记住这一条非常好用的公式就行。。。。

m*n = 最大公约数*最小公倍数~

                  

抱歉!评论已关闭.