质因数分解法求公约数c++

质因数分解法是一种用于求两个或多个整数最大公约数（GCD，Greatest Common Divisor）的有效算法。在C++中，我们可以先将每个数分解成质因数的乘积，然后找出它们共有的质因数，最后通过这些公共质因数相乘得到GCD。

以下是基本步骤：

1. **质因数分解**：对输入的每个数`num1`和`num2`，分别找到其所有的质因数。这通常可以使用循环和除法来完成，每次除以当前最小的质数（如2、3等），直到除尽为止。

vector<int> primeFactors(int num) {
    vector<int> factors;
    for (int i = 2; i * i <= num; ++i) {
        while (num % i == 0) {
            factors.push_back(i);
            num /= i;
        }
    }
    if (num > 1)
        factors.push_back(num); // 如果num还有剩余，说明它是最后一个质因子
    return factors;
}

2. **查找公共质因数**：遍历`num1`和`num2`的质因数列表，找出它们共同的质因数，并把它们添加到结果集合中。

3. **计算GCD**：最后，将找到的所有公共质因数相乘，即得到这两个数的最大公约数。

int gcdUsingPrimeFactors(vector<int>& factors1, vector<int>& factors2) {
    int result = 1;
    for (int factor : factors1) {
        if (find(factors2.begin(), factors2.end(), factor) != factors2.end()) {
            result *= factor;
        }
    }
    return result;
}

// 调用函数
int main() {
    int num1 = 18, num2 = 24;
    auto factors1 = primeFactors(num1);
    auto factors2 = primeFactors(num2);
    int gcd = gcdUsingPrimeFactors(factors1, factors2);
    cout << "The GCD of " << num1 << " and " << num2 << " is: " << gcd << endl;
    return 0;
}