求解n个数的最大公约数c++代码

以下是求解n个数的最大公约数的C++代码：

#include <iostream>
using namespace std;

int gcd(int a, int b) { // 求两个数的最大公约数
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int result = arr[0];
    for (int i = 1; i < n; i++) {
        result = gcd(result, arr[i]);
    }

    cout << "最大公约数为：" << result << endl;

    return 0;
}

首先输入n，接着输入n个数到数组中，然后利用辗转相除法求解最大公约数，最后输出结果。

相关问题

求n个数的最大公约数c++代码

以下是使用欧几里得算法求解n个数的最大公约数的C++代码：

#include <iostream>
using namespace std;

int gcd(int a, int b) { 
    if (b == 0) 
        return a; 
    return gcd(b, a % b); 
} 

int findGCD(int arr[], int n) { 
    int result = arr[0]; 
    for (int i = 1; i < n; i++) 
        result = gcd(arr[i], result); 
    return result; 
} 

int main() {
    int n;
    cout << "Enter the number of integers: ";
    cin >> n;
    int arr[n];
    cout << "Enter " << n << " integers: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "The GCD of " << n << " integers is: " << findGCD(arr, n) << endl;
    return 0;
}

在该代码中，`gcd()` 函数使用了欧几里得算法（又称辗转相除法）来计算两个数的最大公约数。`findGCD()` 函数则使用循环，来计算多个数的最大公约数。

分解质因数法求两个数 的最大公约数C++代码

以下是使用分解质因数法求解两个数最大公约数的Python代码：

def prime_factors(n):
    """返回n的所有质因子"""
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def gcd(a, b):
    """返回a和b的最大公约数"""
    a_factors = prime_factors(a)
    b_factors = prime_factors(b)
    gcd_factors = []
    for factor in a_factors:
        if factor in b_factors:
            gcd_factors.append(factor)
            b_factors.remove(factor)
    if gcd_factors:
        return reduce(lambda x, y: x*y, gcd_factors)
    else:
        return 1

使用`prime_factors`函数分别获取a和b的质因子，然后将两个列表中相同的因子添加到`gcd_factors`列表中，最后将`gcd_factors`中的所有元素乘积作为结果返回。如果没有相同质因子，则最大公约数为1。