質數與因數

質數判斷

要判斷一個數 是否是質數，最暴力的方式是檢查它有沒有除了 1 和 以外的因數，時間複雜度是 。

因為一個合數 一定會有一個 的因數，所以其實只要檢查到 就好，時間複雜度會是 。

質數篩

找 以內的質數，暴力找的話時間會是 ，要更快的話就要用到質數篩。

如果發現了一個質數 ，就會知道 的倍數都不是質數，這個時候就可以把它們刪掉。記錄每一個數被刪掉了沒，從 2 開始看，如果沒被刪掉就表示它是質數，然後去刪掉它的所有倍數，這麼做的時間複雜度是

（見素數的倒數之和）

注意到如果目前數字是 ，對於 ， 肯定已經被更小的數字刪過了，所以可以從 倍開始刪，這樣可以做一點常數優化。

1
2
3
4
5
6
7
8
9
10

vector<bool> isprime(n + 1, true);
vector<int> prime;
for(int i = 2; i <= n; i++){
    if(!isprime[i]) continue;
    prime.eb(i);
    for(int j = i; (ll) i * j <= n; j++){
        isprime[i * j] = false;
    }
}

每一個數被刪到的次數會是「平方不超過它本身的質因數」數量，那有沒有辦法讓每個數都只刪到一次呢？

做法是對於每一個數，刪掉它的「不超過它的最小質因數的質數」倍數。假設 的最小質因數是 ， 是一個 的質數，那麼 的最小質因數肯定是 ，也就是說，一個合數只會被「它除以它的最小質因數」刪掉，得出每個合數只會被刪到一次，複雜度就變成 ，因為複雜度是線性，稱為線性篩。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

vector<int> lpf(n, 1); //每個數的最小質因數
vector<int> prime; //找到的質數

for(int i = 2; i <= n; i++){
    if(lpf[i] == 1){
        lpf[i] = i;
        prime.eb(i);
    }
    for(int j : prime){
        if(i * j > n) break;
        lpf[i * j] = j;
        if(j == lpf[i]) break;
    }
}

質因數分解

暴力找一個數的質因數，複雜度會是 。事實上一個數 頂多只會有一個 的質因數，所以可以只枚舉 到 ，檢查它們是不是 的因數，從 除掉之後，剩下如果 ，那剩下來的數字也是它的質因數，這樣複雜度就是 。

如果要找很多個數的質因數，那也可以利用剛剛線性篩得到的最小質因數。 質因數分解後的數字數量（重複也算）頂多只會有 個，因為所有的質數都 ，因此只要不斷把 的最小質因數除掉，就可以在 做好一個數的質因數分解。

1
2
3
4
5
6
7
8
9
10

vector<pii> pf; //質因數分解的結果，每一項記為 (底數, 指數)

while(x > 1){
    int d = lpf[x];
    pf.eb(mp(d, 0));
    while(x % d == 0){
        pf.back().second++;
        x /= d;
    }
}