埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.~194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。

• 中文名称 埃拉托色尼筛选法
• 外文名称 the Sieve of Eratosthenes
• 简称 埃氏筛法
• 提出 古希腊数学家埃拉托色尼

埃氏筛法步骤

　　(1)先把1删除(现今数学界1既不是质数也不是合数)

　　(2)读取队列中当前最小的数2，然后把2的倍数删去

　　(3)读取队列中当前最小的数3，然后把3的倍数删去

　　(4)读取队列中当前最小的数5，然后把5的倍数删去

　　(5)读取队列中当前最小的数7，然后把7的倍数删去

　　(6)如上所述直到需求的范围内所有的数均删除或读取

　　注:此处的队列并非数据结构队列，如需保留运算结果，处于存储空间的充分利用以及大量删除操作的实施，建议采用链表的数据结构。

　　#include <stdio.h>

　　#define SIZE 10000

　　int main( void ) {

　　int i = 0; // 表示整数和对应的下标.

　　int j = 0; // 表示正在处理的j的倍数从2开始到j * k < SIZE.

　　int flag[SIZE] = {0}; // 下标表示整数内容,标识是否是质数.

　　flag[0] = flag[1] = 0; // 0和1不是质数.

　　for( i = 2; i < SIZE; ++i ) { // 除了0和1其它默认全是质数.

　　flag[i] = 1;

　　}

　　// 处理质数的倍数.

　　for( sum = SIZE, i = 0; i < SIZE; ++i ) {

　　if( 1 == flag[i] ) {

　　for( j = 2; i * j < SIZE; ++j ) {

　　flag[i * j] = 0;

　　}

　　}

　　}

　　// 打印质数.

　　for( i = 0; i < SIZE; ++i ) {

　　if( 1 == flag[i] ) {

　　printf( "%dn", i );

　　}

　　}

　　return 0;

　　}

C++

　　基本算法

　　高效利用cache的算法

　　其中包含伪代码

　　long CacheFriendlySieve(long n){

　　long count=0;

　　long m=(long)sqrt((double)n);

　　bool* composite=new bool[n+1];

　　memset(composite,0,n);

　　long* factor=new long[m];

　　long* striker=new long[m];

　　longn_factor=0;

　　for(long i=2;i<m;++i)

　　if(!composite[i]){

　　++count;

　　striker[n_factor]=Strike(composite,2*i;i,m);

　　factor[n_factor++]=i;

　　}

　　//将筛划分成大小为sqrt(n)的窗口

　　for(long window=m+1;window<=n;window+=m){

　　long limit=min(window+m-1,n);

　　for(long k=0;k<n_factor;++k){

　　//Strike遍历窗口大小为sqrt(n)的部分数组

　　Striker[k]=Strike();

　　for(long i=window;i<limit;++i)

　　if(!composite[i])

　　++count;

　　}

　　delete[] striker;

　　delete[] factor;

　　delete[] composite;

　　return count;

　　}

　　}

java

　　//Sieve.java

　　import java.util.*;

　　/**

　　This program runs the sieve of Eratprstjemes benchmark.

　　It computes all primes up to 2,000,000

　　*/

　　public class Sieve{

　　public static void main(String[] args){

　　int n = 2000000;

　　long start = System.currentTimeMillis();

　　BitSet b = new BitSet(n+1);

　　int count = 0;

　　int i;

　　for(i = 2; i<=n; i++)

　　b.set(i);

　　i = 2;

　　while(i*i<=n){/*sqrt(n),思考为什么是到这个数后面的数就都确定了,在往上加的话,相对于i的另一个数就是比i小的数,计算重复*/

　　if(b.get(i)){//如果该位是质数

　　count++;

　　int k=i*i;

　　while(k<=n){

　　b.clear(k);

　　k+=i;//k是i的倍数,将第k位移除

　　}

　　}

　　i++;

　　}

　　while(i<=n){//计算sqrt(n)后面的数

　　if(b.get(i))

　　count++;

　　i++;

　　}

　　long end = System.currentTimeMillis();

　　System.out.println(count + "primes");

　　System.out.println((end - start) + "milliseconds");

　　}

　　}

pascal

　　maxfactor:=trunc(sqrt(maxp));//筛法求素数

　　fillchar(sieve,sizeof(sieve),true);

　　for i:=2 to maxfactor do

　　if sieve[i] then

　　begin

　　newp:=i+i;

　　while newp<=maxp do

　　begin

　　sieve[newp]:=false;

　　newp:=newp+i;//每次取出这个数的倍数

　　end;

　　end;