埃拉托斯特尼筛法

埃拉托斯特尼筛法通过不断地标记当前质数的所有倍数为合数，从而取得最小的未标记整数为下一个質數。不过，在实际使用此筛法寻找一个范围内的質數时，不需要检查范围内所有整数，也不需要对每个質數都标记其所有的倍数。

1. 寻找${\displaystyle N}$ 以内的質數时，若找到了一个大于${\displaystyle {\sqrt {N}}}$ 的质数，则剩余的所有尚未标记的数也都是質數。

   证明：若这些尚未标记的数中有任意一个为合数，设之为${\displaystyle m}$ ，则${\displaystyle m}$ 必定是除1与自身以外的两个因数的乘积。但既然${\displaystyle m}$ 尚未被标记，则所有小于等于${\displaystyle {\sqrt {N}}}$ 的数均不是${\displaystyle m}$ 的因数。故这两个因数必然都大于${\displaystyle {\sqrt {N}}}$ ，则${\displaystyle m}$ 不可能在${\displaystyle N}$ 以内^{[3]:103-104[4]:4}。

2. 标记某一質數${\displaystyle p}$ 的倍数时，不需要每次皆从${\displaystyle 2p,3p,\ldots }$ 开始，而可直接从${\displaystyle p^{2}}$ 开始标记。

   证明：所有较${\displaystyle p^{2}}$ 更小的${\displaystyle p}$ 的倍数必然拥有一个更小的质数为其因数，故在标记之前的质数的倍数时它们已经被标记过了^[5]。

若要找出25以内的所有质数，使用如上述改进过的埃拉托斯特尼筛法的具体过程如下：

1. 列出2以後所有數：

   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

2. 记录質数2，由2²=4开始划去2的倍数：

   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

3. 记录下一質数3，由3²=9开始划去3的倍数：

   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

4. 记录下一質数5，由5²=25开始划去5的倍数：

   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

5. 下一質数为7，而7²=49>25，故剩余所有未标记的数皆为質数：

   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

由此得到25內的質数为2，3，5，7，11，13，17，19，23。

以上的算法可用以下伪代码表示：

输入：整数n > 1 设A为布尔值矩阵，下标是2至n的整数，初始时全部设成true。  for i = 2, 3, 4, ..., 不超过${\displaystyle {\sqrt {n}}}$ ：  if A[i]为true：    for j = i2, i2+i, i2+2i, i2+3i, ..., 不超过n：      A[j] := false 输出：使A[i]为true的所有i。

埃拉托斯特尼筛法的时间复杂度为${\displaystyle O(n\log(\log n))}$ ；相比之下，若是通过对范围内每个整数进行试除法来找出范围内的质数，则其时间复杂度为${\displaystyle O(n{\sqrt {n}})}$ ^[1]:13-14[5]。

Python 3.6-3.10 编辑

def eratosthenes(n):    is_prime = [True] * (n + 1)    for i in range(2, int(n ** 0.5) + 1):        if is_prime[i]:            for j in range(i * i, n + 1, i):                is_prime[j] = False    return [x for x in range(2, n + 1) if is_prime[x]]print(eratosthenes(120))

C語言 编辑

int prime[100005];bool is_prime[1000005];int eratosthenes(int n) {    int p = 0;    for (int i = 0; i <= n; i++) {        is_prime[i] = true;    }    is_prime[0] = is_prime[1] = 0;    for (int i = 2; i <= n; i++) {        if (is_prime[i]) {            prime[p++] = i;            if (1ll * i * i <= n) {                for (int j = i * i; j <= n; j += i) {                    is_prime[j] = 0;                }            }        }    }    return p;}

C語言新版

#include <stdio.h>#include <stdlib.h>/* N: positive integer   verbose: 1 -- print all prime numbers < N, 0 -- no print   return total number of prime numbers < N.    return -1 when there is not enough memory.*/int eratosthenesSieve(unsigned long long int N, int verbose) {  // prime numbers are positive, better to use largest unsiged integer  unsigned long long int i, j, total; // total: number of prime numbers < N  _Bool *a = malloc(sizeof(_Bool) * N);  if (a == NULL) {    printf("No enough memory.\n");    return -1;  }    /* a[i] equals 1: i is prime number.     a[i] equals 0: i is not prime number.     From beginning, set i as prime number. Later filter out non-prime numbers  */  for (i = 2; i < N; i++) {    a[i] = 1;   }  // mark multiples(<N) of i as non-prime numbers  for (i = 2; i < N; i++) {    if (a[i]) { // a[i] is prime number at this point      for (j = i; j < (N / i) + 1; j++) {/* mark all multiple of 2 * 2, 2 * 3, as non-prime numbers;   do the same for 3,4,5,... 2*3 is filter out when i is 2   so when i is 3, we only start at 3 * 3*/a[i * j] = 0;      }    }  }  // count total. print prime numbers < N if needed.  total = 0;  for (i = 2; i < N; i++) {    if (a[i]) { // i is prime number      if (verbose) {printf("%llu\n", i);      }      total += 1;    }  }  return total;}int main() {  unsigned long long int a1 = 0, a2 = 0, N = 10000000;    a1 = eratosthenesSieve(N, 1); // print the prime numbers  printf("Total of prime numbers less than %llu is : %llu\n", N, a1);    a2 = eratosthenesSieve(N, 0); // not print the prime numbers  printf("Total of prime numbers less than %llu is : %llu\n", N, a2);    return 0;}

C++ 编辑

#include <vector>auto eratosthenes(int upperbound) {  std::vector<bool> flag(upperbound + 1, true);  flag[0] = flag[1] = false; //exclude 0 and 1  for (int i = 2; i * i <= upperbound; ++i) {    if (flag[i]) {      for (int j = i * i; j <= upperbound; j += i)        flag[j] = false;    }  }  return flag;}

R 编辑

eratosthenes <- function(n) {  if (n == 1) return(NULL)  if (n == 2 | n == 3) return(2:n)  numbers <- 2:n  primes <- rep(TRUE, n-1)  for (i in 2:floor(sqrt(n))) {    if (primes[i-1]) {      for (j in seq(i * i, n, i))        primes[j-1] <- FALSE    }  }  return(numbers[primes])}

JavaScript 编辑

const countPrimes = function (n) {  const isPrime = new Array(n).fill(true);  for (let i = 2; i <= Math.sqrt(n); i++) {    if (isPrime[i]) {      for (let j = i * i; j <= n; j += i) {        isPrime[j] = false;      }    }  }  let count = 0;  for (let i = 2; i < n; i++) {    if (isPrime[i]) {      count++;    }  }  return count;};

1. ^ ^{1.0 1.1} Stefan Hougardy; Jens Vygen. Algorithmic Mathematics. Cham: Springer International Publishing Switzerland. 2016. ISBN 978-3-319-39558-6. 
2. ^ Jean-Luc Chabert. A History of Algorithms: From the Pebble to the Microchip. Berlin, Heidelberg: Springer-Verlag. 1999. ISBN 978-3-642-18192-4. 
3. ^ George M. Phillips. Mathematics Is Not a Spectator Sport. New York: Springer-Verlag. 2005. ISBN 978-0-387-28697-6. 
4. ^ G. H. Hardy; E. M. Wright. An Introduction to the Theory of Numbers (Fourth Edition). Oxford: Clarendon Press. 1960. ISBN 978-0-19-853310-8. 
5. ^ ^{5.0 5.1} Melissa E. O'Neill. The Genuine Sieve of Eratosthenes (PDF). Journal of Functional Programming. 2009, 19 (1): 95–106. doi:10.1017/S0956796808007004. 

• Interactive animation (需要JavaScript) （页面存档备份，存于互联网档案馆）
• 打印质数的各种算法 （页面存档备份，存于互联网档案馆）
• 筛法小结 (Eratosthenes/Euler)
• 欧拉函数线性筛法详解 （页面存档备份，存于互联网档案馆）（欧拉函数线性筛）
• 一般筛法求素数+快速线性筛法求素数(较好理解) （页面存档备份，存于互联网档案馆）