用质因数求解最大公约数（gcd）和最小公倍数（lcm）

用质因数求解最大公约数（gcd）

思路分析：

1、质因数：(素因数或质因子)他指的是能整除给定正整数的质数。例如：36可以分解为223*3，其中2和3就是质因数。
2、质因数求解最大公约数：
对每个数进行质因数分解；
找出所有数的共有质因数，并取每个共有质因数的最低次幂；
将这些最低次幂的质因数想乘，得到的结果就是这些数的最大公约数。
gcd（a，b）=pi的min（ai，bi）次方 * pj的min（aj，bj）次方

code：

#include <iostream>
#include <unordered_map>
#include <cmath>

// 辅助函数：检查一个数是否是质数
bool is_prime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

// 辅助函数：找到并返回一个数的所有质因数及其次数
std::unordered_map<int, int> find_prime_factors(int n) {
    std::unordered_map<int, int> factors;
    for (int i = 2; i <= std::sqrt(n); ++i) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    // 如果n仍然大于1，那么它本身就是一个质数
    if (n > 1) {
        factors[n] = 1;
    }
    return factors;
}

// 使用质因数分解来求解最大公约数
int gcd_by_prime_factors(int a, int b) {
    std::unordered_map<int, int> factors_a = find_prime_factors(a);
    std::unordered_map<int, int> factors_b = find_prime_factors(b);

    int gcd = 1;
    for (const auto& factor_a : factors_a) {
        int prime = factor_a.first;
        int count_a = factor_a.second;

        // 查找b的质因数中是否有prime，并取其最小次数
        auto iter_b = factors_b.find(prime);
        if (iter_b != factors_b.end()) {
            int count_b = iter_b->second;
            int min_count = std::min(count_a, count_b);
            gcd *= std::pow(prime, min_count);
        }
    }

    // 还需要考虑b中独有的质因数（如果a中没有的话）
    for (const auto& factor_b : factors_b) {
        if (factors_a.find(factor_b.first) == factors_a.end()) {
            int prime = factor_b.first;
            int count_b = factor_b.second;
            // 但由于我们只关心共有的质因数，所以这里不增加gcd
        }
    }

    return gcd;
}

int main() {
    int a = 24;
    int b = 36;
    std::cout << "GCD of " << a << " and " << b << " is: " << gcd_by_prime_factors(a, b) << std::endl;
    return 0;
}

用质因数求解最小公倍数（lcm）

思路分析：

1、质因数：(素因数或质因子)他指的是能整除给定正整数的质数。例如：36可以分解为223*3，其中2和3就是质因数。
2、质因数求解最小公倍数：
对每个数进行质因数分解；
找出所有数的共有质因数，并取每个共有质因数的最高次幂；
将这些最高次幂的质因数想乘，得到的结果就是这些数的最小公倍数。
lcm（a，b）=pi的max（ai，bi）次方 * pj的max（aj，bj）次方

code：

#include <iostream>
#include <unordered_map>
#include <cmath>

// 辅助函数：找到并返回一个数的所有质因数及其次数
std::unordered_map<int, int> find_prime_factors(int n) {
    std::unordered_map<int, int> factors;
    for (int i = 2; i <= std::sqrt(n); ++i) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    // 如果n仍然大于1，那么它本身就是一个质数
    if (n > 1) {
        factors[n] = 1;
    }
    return factors;
}

// 使用质因数分解来求解最小公倍数
int lcm_by_prime_factors(int a, int b) {
    std::unordered_map<int, int> factors_a = find_prime_factors(a);
    std::unordered_map<int, int> factors_b = find_prime_factors(b);

    // 合并两个数的质因数，取最大次数
    for (const auto& factor_b : factors_b) {
        factors_a[factor_b.first] = std::max(factors_a[factor_b.first], factor_b.second);
    }

    // 计算最小公倍数
    int lcm = 1;
    for (const auto& factor : factors_a) {
        lcm *= std::pow(factor.first, factor.second);
    }

    return lcm;
}

int main() {
    int a = 24;
    int b = 36;
    std::cout << "LCM of " << a << " and " << b << " is: " << lcm_by_prime_factors(a, b) << std::endl;
    return 0;
}