论坛 › C\C++交流 › 用C++求最大公约数

香蕉那个不拿拿 发表于 2023-7-16 15:24:15

用C++求最大公约数

用计算机傻算公约数
先穷举所有因数
再一一配对。
#include<iostream>
using namespace std;
int main()
{
        int max = 0;
        long long a ;
        long long b ;
        int anumber,bnumber;
        cin>>anumber>>bnumber;
        int counta = 0,countb = 0;
        for (int i = 1;i <= anumber / 2;i++)
        {
                if (anumber % i== 0)
                {
                        counta+=1;
                        a = i;
                        a = anumber/ i;
                        counta+=1;
                }
        }
        for (int i = 1;i <= bnumber / 2;i++)
        {
                if (bnumber % i== 0)
                {
                        countb += 1;
                        b = i;
                        b = bnumber/ i;
                        countb += 1;
                }
        }
        for (int i = 1;i <= counta;i++)
        {
                for (int j = 1;j <= countb;j++)
                {
                        if (a == b)
                        {
                                if (a > max)
                                {
                                        max = a;
                                }
                        }
                }
        }
        cout<<max;
}

zhangjinxuan 发表于 2023-7-16 20:11:38

欧几里得算法。

原理如下：

gcd(x, y) = gcd(y, x % y) (y != 0)
gcd(x, 0) = x

因此，我们可以写出如下的求最大公因数代码：

#include <bits/stdc++.h>
using namespace std;

template<typename T>
T gcd(T x, T y) {
        return y ? gcd(y, x % y) : x;
}

int main() {
        long long a, b;
        printf("Enter two 64 bit numbers: ");
        scanf("%lld%lld", &a, &b);
        printf("gcd(%lld, %lld) = %lld\n", a, b, gcd(a, b));
    return 0;
}

香蕉那个不拿拿 发表于 2023-7-17 13:52:28

zhangjinxuan 发表于 2023-7-16 20:11
欧几里得算法。

原理如下：


是
有一个辗转相除法
更简单

查看完整版本: 用C++求最大公约数