如何在C++中優(yōu)化分解質(zhì)因數(shù)的代碼

c++
小樊
102
2024-07-14 08:00:26
欄目: 編程語言

在C++中優(yōu)化分解質(zhì)因數(shù)的代碼可以使用試除法和埃氏篩法等算法來減少時(shí)間復(fù)雜度。以下是一個(gè)使用試除法優(yōu)化的例子：

#include <iostream>
#include <vector>

void primeFactors(int n) {
    // 輸出所有的 2
    while (n % 2 == 0) {
        std::cout << 2 << " ";
        n = n / 2;
    }
  
    // n 現(xiàn)在一定是奇數(shù)，可以跳過偶數(shù)
    for (int i = 3; i * i <= n; i = i + 2) {
        // 輸出所有的 i
        while (n % i == 0) {
            std::cout << i << " ";
            n = n / i;
        }
    }
  
    // n 現(xiàn)在可能是一個(gè)大于 2 的素?cái)?shù)
    if (n > 2) {
        std::cout << n << " ";
    }
}

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

這個(gè)代碼使用試除法來分解質(zhì)因數(shù)，首先判斷是否能被2整除，然后再循環(huán)判斷是否能被奇數(shù)整除。這樣可以減少不必要的循環(huán)次數(shù)，提高代碼的效率。

另外，也可以使用埃氏篩法來預(yù)處理質(zhì)數(shù)表，然后使用質(zhì)數(shù)表來進(jìn)行分解質(zhì)因數(shù)，這樣可以更快地找到質(zhì)因數(shù)。

0 踩