如何在C++中优化分解质因数的代码

c++

小樊

106

2024-07-14 08:00:26

栏目: 编程语言

在C++中优化分解质因数的代码可以使用试除法和埃氏筛法等算法来减少时间复杂度。以下是一个使用试除法优化的例子：

#include <iostream>
#include <vector>

void primeFactors(int n) {
    // 输出所有的 2
    while (n % 2 == 0) {
        std::cout << 2 << " ";
        n = n / 2;
    }
  
    // n 现在一定是奇数，可以跳过偶数
    for (int i = 3; i * i <= n; i = i + 2) {
        // 输出所有的 i
        while (n % i == 0) {
            std::cout << i << " ";
            n = n / i;
        }
    }
  
    // n 现在可能是一个大于 2 的素数
    if (n > 2) {
        std::cout << n << " ";
    }
}

int main() {
    int n = 315;
    primeFactors(n);
    return 0;
}

这个代码使用试除法来分解质因数，首先判断是否能被2整除，然后再循环判断是否能被奇数整除。这样可以减少不必要的循环次数，提高代码的效率。

另外，也可以使用埃氏筛法来预处理质数表，然后使用质数表来进行分解质因数，这样可以更快地找到质因数。

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

如何在C++中优化分解质因数的代码

最新问答

相关标签