歐拉篩是O(n)復雜度的篩素數算法，1秒內埃篩能處理1e6的數據，而1e7的數據就必須用歐拉篩了。

埃篩的基本思想是：素數的倍數一定是合數。
歐拉篩基本思想是：任何數與素數的乘積一定是合數

算法概述：
遍歷[2, n]的所有數i，內層循環遍歷已經找到的素數prime[j]，將i * prime[j] 標記為合數。
內層循環的最后，檢查如果prime[j]是i的最小質因子，則退出到外層循環，因為prime[j+1] * i肯定已經被篩過了。

代碼：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e7 + 5; int isPrime[MAXN]; // isPrime[i] 表示i是否素數 int prime[MAXN]; // 按順序存素數 int cnt = 0; // 素數個數// 找出n以內的全部（cnt個）素數 void euler(int n) { memset(isPrime, 1, sizeof(isPrime)); // 默認全是素數cnt = isPrime[0] = isPrime[1] = 0; // 素數個數清零，標記0和1不是素數// 已知 [2, n] 之間的每一個數 i 與任意素數的乘積一定是合數，// 遍歷已找到全部素數 prime[j]，將 i * prime[j] 標記為合數for (int i = 2; i <= n; i++) {if (isPrime[i]) prime[cnt++] = i; // 找到素數 for (int j = 0; j < cnt; j++) { // 遍歷已找到的素數if (i * prime[j] > n) break; // 越界跳出isPrime[i * prime[j]] = 0; // 標記合數// 避免重復篩除的關鍵代碼// 當找到i的最小質因子 prime[j] 時，退出循環if (i % prime[j] == 0) break;}} }int main() {int n; cin >> n;euler(n);// for (int i = 0; i < cnt; ++i) cout << prime[i] << endl; // 打印素數cout << "cnt:" << cnt << endl;return 0; }

總結

以上是生活随笔為你收集整理的线性筛素数（欧拉筛）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。