質數和合數及求質數

一個大于 1 的自然數，除了 1 和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數。其中，質數又稱素數。有的資料用的詞不同，但質數和素數其實是一回事。

規定 1 既不是質數也不是合數。

試除法判斷質數

• 對于一個數 $x$，根據定義，可以從 $[2,x?1]$ 一個一個嘗試，判斷 $x$ 能否被整除。

但是，沒有必要每一個都去判斷。因為 $a$ 如果是 $x$ 的約數，那么 $x/a$ 也是 $x$ 的約數。因此，我們僅需判斷較小的 $a$ 是否是 $x$ 的約數，沒有必要再去看看 $x/a$。那么，僅需枚舉到 $\sqrt{x}$ 即可。

試除法實現：

bool prim(int x) {if (x < 2)return false;for (int i = 2; i <= x / i; i++)//i*i<=x，所以i<=x/i，這是防溢出寫法if (x % i == 0)return false;return true;
}

時間復雜度：因為是枚舉到$\sqrt{n}$，所以時間復雜度為$O(\sqrt{N})$。

模板題：

P5736 【深基7.例2】質數篩 - 洛谷

#include<bits/stdc++.h>
using namespace std;bool prim(int x) {if (x < 2)return false;for (int i = 2; i <= x / i; i++)if (x % i == 0)return false;return true;
}int main() {int n; cin >> n;for (int x = 0; n--;) {cin >> x;if (prim(x))cout << x << ' ';}return 0;
}

Eratosthenes篩選法（埃氏篩）

模板題：P3383 【模板】線性篩素數 - 洛谷

在很多場景我們需要知道[2, n]內有多少個質數，或正數、倒數第$k$個質數是多少。$n$ 很有可能特別大，此時傳統的試除法一個一個判斷顯然會很慢甚至無法在規定時間內完成判斷。因此需要使用其他算法來篩選出指定范圍內的質數。

Eratosthenes篩選法基本思想：質數的倍數一定不是質數。

實現方法：用一個長度為 $N+1$ 的數組vis保存信息（0 表示質數，1 表示非質數），先假設所有的數都是質數（初始化為 0），從小到大枚舉每一個質數 $x$，把 $x$ 的倍數都標記為非質數（置為 1）。當從小到大掃描時掃描到一個數 $x$ ，若它尚未被標記，則它不能被 $2～x?1$ 之間的任何數整除，該數就是質數。

整數 1 特殊處理即可。在篩數的時候可以從$x^2$開始篩，因為小于$x$的合數是被篩選過的。

//Eratosthenes篩（埃氏篩）
void get_prim(vector<int>&vis, vector<int>&ans) {for (size_t i = 2; i < vis.size(); i++) {if (vis[i])continue;//記錄素數ans.push_back(i);//從i*i開始，因為小于i的合數已經被篩掉了for (size_t j = i * i; j < vis.size(); j+=i)vis[j] = true;//篩掉合數}
}

時間復雜度（推薦直接記結論）：$O(n\log \log n)$。這里$n$實際就是vis.size()。

嚴謹的數學推導：埃氏篩法的時間復雜度的詳細證明-CSDN博客

P3383 【模板】線性篩素數 - 洛谷參考程序（埃氏篩）：

#include<bits/stdc++.h>
using namespace std;void Eratosthenes(vector<bool>& vis, vector<int>& ans) {for (size_t i = 2; i < vis.size(); i++) {if (vis[i])continue;ans.push_back(i);for (size_t j = i * i; j < vis.size(); j += i)vis[j] = true;}
}int main() {int n, q,num;scanf("%d %d", &n, &q);vector<bool>vis(n + 1, false);vector<int>ans;Eratosthenes(vis, ans);//埃氏篩while (q--) {scanf("%d", &num);cout << ans[num - 1] << endl;}return 0;
}

線性篩（歐拉篩）

線性篩法，又稱歐拉篩法。在埃氏篩法中，它會將一個合數重復多次標記。如果能讓每個合數都只被標記一次，那么時間復雜度就可以降到 $O(n)$ 。

我們的做法是，讓每一個合數被它的最小質因數篩掉。

void get_prim(vector<int>& vis, vector<int>& ans) {for (size_t i = 2; i < vis.size(); i++) {if (!vis[i])//被標記為true時是合數ans.push_back(i);//1uLL是為了讓size_t強制轉換成unsigned long long防止溢出for (size_t j = 0; 1uLL * i * ans[j] < vis.size(); j++) {//篩掉合數vis[i * ans[j]] = true;//i是質數的倍數時停止，當i正好為最后一個質數時循環終止if (i % ans[j] == 0)break;}}
}

i%ans[j]==0這個判定條件能讓每一個合數被自己的最小質因數篩掉。

1. 如果 i 是合數，枚舉到最小質因數的時候跳出循環
2. 如果 i 是質數，枚舉到自身時跳出循環
   注意，在篩的過程中，我們還能知道 p[j] 是 i 的最小質因數

這個算法最多遍歷2遍數組，也就是說實際的時間復雜度是$O(2n)$。

很多和數學有關的算法都是在歐拉篩的基礎上實現（例如積性函數），因此歐拉篩很重要，需要理解這個算法的本質。

P3383 【模板】線性篩素數 - 洛谷參考程序（歐拉篩）：

#include<bits/stdc++.h>
using namespace std;void Euler(vector<bool>& vis, vector<int>& ans) {for (size_t i = 2; i < vis.size(); i++) {if (!vis[i])ans.push_back(i);for (size_t j = 0; 1uLL * i * ans[j] < vis.size(); j++) {vis[i * ans[j]] = true;if (i % ans[j] == 0)break;}}
}int main() {int n, q,num;scanf("%d %d", &n, &q);vector<bool>vis(n + 1, false);vector<int>ans;Euler(vis, ans);//歐拉篩while (q--) {scanf("%d", &num);cout << ans[num - 1] << endl;}return 0;
}

質數有關OJ列舉

P1835 素數密度 - 洛谷

P1835 素數密度 - 洛谷

因為$1\le L\le R\le 2^{31}$，無論是埃氏篩還是線性篩，在空間上會超限，在時間上遍歷$2^{31}$，$O(n)$的算法也無法在1秒內完成。

根據試除法，求一個數$r$是否是質數，只需枚舉$[1,\sqrt{r}]$。

所以代碼思路：

• 先找出$[1,\sqrt{R}]$內的質數，再利用這些質數將$[L,R]$內的合數標記。$\sqrt{R}$的數據范圍是$[2,2^{16}]$，$2^{16}=65536$，在可接受范圍內，用埃氏篩或歐拉篩都可以。
• 找到這些質數在$[L,R]$內的最小合數后，用埃氏篩的做法標記$[L,R]$內的其他合數。首先需要找到質數在$[L,R]$的最小倍數。
  所以整體思路是埃氏篩 + 歐拉篩。

找質數在$[L,R]$內的最小倍數：假設$p\in [1,\sqrt{R}]$且$p$是質數，則$kp\ge L$，$k\ge ?\frac{L}{p}?$，也就是說可以通過左端點除以質數并向上取整，再乘質數，即可得到最小倍數。即$?\frac{L}{p}?\times p$。

在計算機中求$?\frac{L}{p}?$，特別是c++默認整數除法/會去除小數部分，所以可以通過對$\frac{L+(p?1)}{p}$向下取整來間接求得$?\frac{L}{p}?$。

• 若$L$是$p$的倍數，后面的$p?1$對整體不構成影響；
• 若不是，則在浮點數的視角，$\frac{L}{p}$會殘留有小數部分，這一部分加上$\frac{p?1}{p}$大于1，所以通過$?\frac{L+(p?1)}{p}?$也能間接求得$?\frac{L}{p}?$。

綜上，$?\frac{L+(p?1)}{p}?=?\frac{L}{p}?$。在代碼中可通過(L+p-1)/p*p得到質數$p$的不小于$L$的最小倍數。

其中需要注意的細節：

1. $L=1$，但1不是質數，所以此時需要從$L=2$開始。
2. $L\in [1,\sqrt{R}]$且$L$可能是質數。
   例如{2,3,5}，要求篩掉[5,25]中的合數，$?\frac{5+5?1}{5}?\times 5=5$，因此會把5篩掉，但5是質數不能被篩掉，因為之前較小的質數已經把部分合數給曬掉了，所以若枚舉到質數$p$，則從$2p$開始篩，因此在使用埃氏篩的方法篩掉合數時可以從$\max (2p,?\frac{L+(p?1)}{p}?)$開始。
3. 因為$R$是有可能到$2^{31}$，數組不可能開這么大，但可以通過小區間[0,R-L]來存儲[L,R]的結果，再開一個$10^6$的數組勉強能接受。
4. 因為數據量整體過大，只有放棄vector轉用一般的數組才能不超時。

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N = 1e6 + 10;
bool vis1[N], vis2[N];//因為超時，不得不換成普通數組
int ans[N], pans;
int L, R;void get_prim() {size_t n = sqrt(R);for (size_t i = 2; i <= n; i++) {if (!vis1[i])ans[++pans]=i;for (size_t j = 1; 1ull * i * ans[j] <= n; j++) {vis1[i * ans[j]] = 1;if (i % ans[j] == 0)break;}}
}int main() {cin >> L >> R;get_prim();L = L == 1 ? 2 : L;for (int i = 1; i <= pans;i++) {int x = ans[i];for (LL i = max(x * 2, (L + x - 1) / x * x);i<=R; i+=x) {vis2[i - L] = 1;}}int cnt = 0;for (int i = L; i <= R; i++) if (!vis2[i - L])++cnt;cout << cnt;return 0;
}

簡單的哥赫巴德猜想和cin優化

UVA543 Goldbach’s Conjecture - 洛谷

1622：Goldbach’s Conjecture

這題是UVA上的題，但可以在信奧網站提交。

素數篩制表，然后查表即可。因為這個猜想至今仍然沒有找到一個反例，所以直接找即可。

因為數據量過大，用cin輸入時需要使用優化手段，或直接用scanf。而且不能用endl。

#include<bits/stdc++.h>
using namespace std;const int N = 1e6 + 1;
bool vis[N];
int ans[N], pans;void get_prim() {for (int i = 2; i < N; i++) {if (!vis[i])ans[++pans] = i;for (int j = 1; 1ull*i * ans[j] < N; j++) {vis[i * ans[j]] = 1;if (i % ans[j] == 0)break;}}
}int main() {ios::sync_with_stdio(0);cin.tie(0);//不用這個對cin進行優化會超時//cout.tie(0);//這個有沒有都不影響get_prim();int n;while (cin>>n, n) {for (int i = 1; i <= pans &&ans[i]<n; i++) {if (!vis[n - ans[i]]) {cout << n << " = " << ans[i] << " + " << n - ans[i] << "\n";break;}}}return 0;
}