<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Sieve - 篩選算法 -------- #### 問題 素數是除了$$ 1 $$和它自身沒有其他數能夠整除的正整數，最小的素數是$$ 2 $$。而不符合該特性的正整數是合數，常見的素數有$$ 2, 3, 5, 7, 9, 11, 13, 17, 19, 23 \dots $$。素數是數論學科中的基礎概念，關于素數的最為著名的問題就是哥德巴赫猜想。 判斷$$ [1 \dots n) $$中哪些是素數，哪些是合數。 #### 解法 按照素數的定理，判斷一個正整數$$ x $$是否為素數，需要遍歷$$ [1 \dots x] $$中所有數字$$ i $$是否能被$$ x $$整除，即$$ x % i = 0 $$。判斷一個數字的時間復雜度為$$ O(n) $$，判斷$$ n $$個數字的時間復雜度為$$ O(n ^ 2) $$。埃拉托斯特尼篩選法（Eratosthenes Sieve）可以更快的完成所有判斷。 設置數組$$ s = [1 \dots n) $$，$$ s[i] $$表示數字$$ i $$是否為素數。初始時顯然有$$ s[1] = false $$。 $$ (1) $$ 以$$ 2 $$為篩子，$$ s[2] = true, s[2 \times 2] = false, s[2 \times 3] = false \dots $$，除了$$ 2 $$本身，所有$$ 2 $$的倍數都不是素數； $$ (2) $$ 以$$ 3 $$為篩子，$$ s[3] = true, s[3 \times 2] = false, s[3 \times 3] = false \dots $$，除了$$ 3 $$本身，所有$$ 3 $$的倍數都不是素數； $$ (3) $$ 以$$ 5 $$為篩子，$$ s[5] = true, s[5 \times 2] = false, s[5 \times 3] = false \dots $$，除了$$ 5 $$本身，所有$$ 5 $$的倍數都不是素數； $$ \cdots $$ 因為顯然偶數中除了$$ 2 $$都是合數，可以跳過所有偶數只考察奇數。 -------- #### 源碼 [Sieve.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/NumberTheory/Sieve.h) [Sieve.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/NumberTheory/Sieve.cpp) #### 測試 [SieveTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/NumberTheory/SieveTest.cpp)