Eratosthenes 篩法是一種用已知的質數尋找其他質數的方法。
方法[]
若要找出不大於任意正整數的質數，
- 首先，將不大於的所有質數列出來。
- 然後將所有介於和之間的所有(正)整數，以上一步驟中列出的質數試除，將其中可被除盡的數給刪除，再將剩下的數以另一質數試除，之後一樣將可除盡的數給刪去，如此反覆。剩下來的數即是不能被任何將不大於的質數整除者，即為質數。
例若要找不大於32的質數，首先取25的平方根，也就是，(正整數中)不大於的質數有2、3、5三個，然後列出5到25間的每個數，也就是以下幾個數：
- 5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25、26、27、28、29、30、31、32
然後先將這些數以2除一次，得以下數列：
- 5、7、9、11、13、15、17、19、21、23、25、27、29、31
注意6、8、10、12、14、16、18、20、22、24、26、28、30、32全都可被2給除盡，因此剩下的數都不可被2給除盡
然後再將剩下的數以3除一次，得以下數列：
- 5、7、11、13、17、19、23、25、29、31
注意9、15、21和27可被3給除盡，因此剩下的數不可被2或3給除盡。
然後再將剩下的數以5除一次，得以下數列：
- 5、7、11、13、17、19、23、29、31
25在此被刪去，剩下的數不可被2、3或5給除盡，它們都是不大於32的質數，用這些數可再去尋找所有不大於1024()的質數。
| 初等数论（学科代码：1101710，GB/T 13745—2009） | |
|---|---|
| 整除理论 | 整除 ▪ 带余除法 ▪ 素数 ▪ 公因数 ▪ 辗转相除法 ▪ 公倍数 ▪ 惟一因子分解定理 ▪ 容斥原理 |
| 同余理论 | 同余 ▪ 同余类（完全代表系，缩同余类） ▪ 同余类的代数结构 ▪ 一次同余方程 ▪ 中国剩余定理 ▪ 线性同余方程组 ▪ 二元一次同余方程组 |
| 剩余理论 | Euler-Fermat 定理 ▪ 原根 ▪ 指数 ▪ 威尔森定理 ▪ K 次剩餘 ▪ 二次剩余 ▪ Legendre 符号 ▪ 二次互反律 ▪ Jacobi 符号 ▪ 二次同余方程 |
| 数论函数 | 除数函数 ▪ 除数和函数 ▪ Euler 函数 ▪ Liouville 函数 ▪ Möbius 反演公式 ▪ 数论函数的卷积 ▪ 数论函数的均值 ▪ Dirichlet 特征 |
| 不定方程 | 二元一次不定方程 ▪ Pythagoras 方程 ▪ 四平方和问题 ▪ 二平方和问题 ▪ Fermat 方程 ▪ 立方和问题 |
| 素数分布 | Eratosthenes 筛法 ▪ 素数定理 ▪ Chebyshev 函数 ▪ Mangoldt 函数 ▪ Euler 恒等式 |
| 所在位置：数学（110）→ 数论（11017）→ 初等数论（1101710） | |