用C++求最大公约数

香蕉那个不拿拿

用计算机傻算公约数
先穷举所有因数
再一一配对。

#include<iostream>
using namespace std;
int main()
{
        int max = 0;
        long long a [5000];
        long long b [5000];
        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 [counta] = i;
                        a [counta + 1] = anumber/ i;
                        counta+=1;
                }
        }
        for (int i = 1;i <= bnumber / 2;i++)
        {
                if (bnumber % i  == 0)
                {
                        countb += 1;
                        b [countb] = i;
                        b [countb + 1] = bnumber/ i;
                        countb += 1;
                }
        }
        for (int i = 1;i <= counta;i++)
        {
                for (int j = 1;j <= countb;j++)
                {
                        if (a[i] == b[j])
                        {
                                if (a[i] > max)
                                {
                                        max = a[i];
                                }
                        }
                }
        }
        cout<<max;
}

zhangjinxuan

欧几里得算法。

原理如下：

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;
}

香蕉那个不拿拿

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

原理如下：

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