埃拉托斯特尼筛法

埃拉托斯特尼筛法（，），簡稱-{zh-cn:埃氏筛; zh-tw:埃氏篩; zh-hk:愛氏篩}-，也称素数筛，是簡單且历史悠久的筛法，用來找出一定範圍內所有質數。

原理是從2開始，將每個質數的各倍數標記成合數。一個質數的各個倍數，是一個差為此質數本身的等差數列。此為這個篩法和試除法不同的關鍵之處，後者是以質數來測試能否整除每個待測數。

質數篩是列出所有小質數的有效方法，得名於古希臘數學家埃拉托斯特尼，並且描述在另一位古希臘數學家尼科馬庫斯所著的《算術入門》中。

作為現代篩法基礎的勒讓德篩法是埃拉托斯特尼篩法的簡單推廣。

算式
定出要筛数值的范围n，找出以内的質數。先用2去筛，把2留下，把2的倍数剔除掉；再用下個質數3筛，把3留下，把3的倍数剔除掉；接下去用下個質數5筛，把5留下，把5的倍数剔除掉，直至夠為止。

步驟

详细列出算法如下：

列出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 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 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的平方，返回第二步：
2之後第一个質数是3，用藍色標記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

得到的質数是2，3。
25仍大于3的平方，再次返回第二步：
3之後第一个質数是5，用綠色標記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
得到的質数是2，3，5。
25是5的平方，篩選完畢。

结论：去掉红色及綠色的数，25內的質数是2，3，5，7，11，13，17，19，23。

演算法

質數篩可用以下-{zh-cn:伪代码;zh-tw:虛擬碼;}-表示：

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

 輸入：整數n > 1
  
 設A為布爾值陣列，指標是2至n的整數，
 初始時全部設成true。
  
  for i = 2, 3, 4, ..., 不超過：
   if A[i]為true：
     for j = i2, i2+i, i2+2i, i2+3i, ..., 不超過n：
       A[j] := false
  
 輸出：使A[i]為true的所有i。;}-

以上演算法可以得到小於等於的所有質數，它的複雜度是。

程式码

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;
};

参见

篩法
卢卡斯-莱默检验法
米勒-拉宾检验
试除法
费马素性检验
孪生素数
三胞胎素数
四胞胎素数
素数判定法则
表兄弟素数
六素数
X²+1素数
勒讓德篩法

参考文献

  or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.

拓展阅读 
Interactive animation (需要JavaScript) 
打印质数的各种算法 
筛法小结 (Eratosthenes/Euler)
欧拉函数线性筛法详解 （欧拉函数线性筛）
一般筛法求素数+快速线性筛法求素数(较好理解) 

素性测试
带有伪代码示例的条目
 
算法