c++实现不超过n的数中的两个数的最小公倍数的最大值

在C++中，要找到不超过给定整数`n`的所有数对中两数的最小公倍数的最大值，可以采用一些算法技巧。首先，我们需要知道求两个数的最小公倍数(LCM)的基本步骤：两数分解质因数然后取每个质因数的最大指数。

下面是一个简单的思路：

1. 遍历所有不大于`n`的数。
2. 对于每一个数`a`，计算它的所有质因子的倍数（直到超过`n`），并找出其中能构成最大最小公倍数的组合。
3. 记录下在这一过程中遇到的最大最小公倍数。

这里需要借助于一个辅助函数来查找每个数的质因子，并更新当前已知的最大最小公倍数。

#include <vector>
#include <cmath>

// Function to find prime factors of a number and store in vector
std::vector<int> primeFactors(int num) {
    std::vector<int> factors;
    for (int i = 2; i * i <= num; ++i) {
        while (num % i == 0) {
            factors.push_back(i);
            num /= i;
        }
    }
    if (num > 1) { // If num is still a prime factor
        factors.push_back(num);
    }
    return factors;
}

// Function to calculate LCM using prime factors
int lcm(int a, int b) {
    std::vector<int> aFactors = primeFactors(a);
    std::vector<int> bFactors = primeFactors(b);

    int lcm = a;
    for (auto& factor : aFactors) {
        int maxPower = std::max((bFactors.end() - std::lower_bound(bFactors.begin(), bFactors.end(), factor)) + 1, static_cast<int>(aFactors.count(factor)));
        lcm *= pow(factor, maxPower);
    }

    return lcm;
}

// Find the maximum LCM among all pairs less than or equal to n
int maxLCMPair(int n) {
    int maxLcm = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            int lcmValue = lcm(i, j);
            if (lcmValue > maxLcm) {
                maxLcm = lcmValue;
            }
        }
    }
    return maxLcm;
}