一、算法簡介

在數論與編程競賽中，求解 $[1,n]$ 范圍內的所有質數是常見的基礎問題。埃拉托色尼篩法（Sieve of Eratosthenes） 是一種古老而高效的算法，可以在 $O(n\log \log n)$ 的時間復雜度內完成這一任務。

---

二、基本思想

埃氏篩的核心思想是：

對于每一個從小到大的質數 $p$，將其所有的倍數（$2p,3p,4p,\dots$）標記為合數。
最終，所有未被標記的數就是質數。

舉例說明：
設 $n=30$，初始認為 $2～30$ 都是質數。
我們從 $2$ 開始，依次把 $4,6,8,\dots$ 標記為合數；
然后處理下一個未被標記的 $3$，再把 $6,9,12,\dots$ 標記為合數；
如此反復，直到 $\sqrt{n}$。

---

三、代碼實現

以下是使用 C++ 編寫的埃氏篩標準模板

#include<iostream>
#include<vector>
using namespace std;const int N = 1e5 + 10; // 設置一個足夠大的常數N，表示數組大小vector<bool> ans(N, true); // 初始化素數表，默認所有數都是素數（true）
vector<int> nums;          // 用于存儲最終得到的所有質數// 篩法主函數：獲取1到n之間的所有素數
void get(int n)
{ans[0] = ans[1] = false; // 0 和 1 不是質數，直接標記為 false// 使用埃氏篩法，從 2 開始依次判斷for (int i = 2; i <= n / i; i++)  // 等價于 i * i <= n{if (ans[i]) // 如果當前數 i 是質數（尚未被篩掉）{// 從 i*i 開始，而不是 2*i：// 因為 i < j < i*i 范圍內的 i 倍數，如 2*i, 3*i 等，已被更小的質數篩掉了for (int j = i * i; j <= n; j += i) // 枚舉 i 的所有倍數{ans[j] = false; // 將 j 標記為合數}}}// 將所有的質數加入 nums 數組for (int k = 2; k <= n; k++){if (ans[k]){nums.push_back(k);}}
}

主函數調用如下：

int main()
{int n;cin >> n; // 輸入要求篩到的最大范圍get(n); // 執行篩法for (auto num : nums){cout << num << " "; // 輸出所有質數}return 0;
}

---

四、關鍵優化說明

1. 為什么從 i * i 開始篩？

因為在遍歷到質數 $i$ 時，小于 $i$ 的質數已經處理了 $2i,3i,...,(i?1)i$ 的倍數。例如：

• $6=2\times 3$ 會在處理 $2$ 時被篩掉；
• $9=3\times 3$ 會在處理 $3$ 時被篩掉。

因此，從 $i\times i$ 開始可以減少重復標記，提升效率。

2. 循環條件 i <= n / i

等價于 i * i <= n，這種寫法可避免整數溢出，建議記住作為一種 防溢出技巧。

---

五、時間與空間復雜度

• 時間復雜度：$O(n\log \log n)$，非常高效
• 空間復雜度：$O(n)$，主要用于布爾數組 ans[]

---

六、樣例輸入輸出

輸入：

100

輸出：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

---

七、適用場景與拓展

• 快速判斷一個數是否為質數（配合布爾數組）
• 枚舉某范圍內的所有質數（如用于歐拉函數、積性函數計算）
• 可拓展為線性篩（Euler 篩）以避免重復標記（時間復雜度為 $O(n)$）

---

八、結語

埃拉托色尼篩法是數論的入門利器，是多種算法的基礎工具。建議熟練掌握并牢記模板結構。同時要理解從 i * i 開始標記的數學依據，避免盲記公式。