埃拉托色尼筛选法
简介埃拉托色尼选筛法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes)提出的一种筛选法。 是针对自然数列中的自然数而实施的，它的容斥原理之完备性条件是p=H~。步骤（1）先把1删除（因为1不是质数）（2）把2留下（最小的偶数质数），然后把2的倍数删去
（3）把3留下，然后把3的倍数删去
（4）把5留下，然后把5的倍数删去
（5）....继续进行下去，直到把所有数要么留下，要么删除。（所有偶数被删去）
可参见右图c语言实现以下给出eratosthenes筛选法的c语言实现。注意此不是最优解。但是是一个比较容易看懂的实现。
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define SIZE 1000000
int main()
{
int i; /*i表示整数和对应的下标*/
int j; /*j表示正要处理的质数j之前的已处理j之后的未处理*/
int k; /*k表示正在处理的j的倍数从2开始到j*k<SIZE*/
int a[SIZE]; /*下标表示整数内容判断是否为质数*/
int *p; /*控制循环*/
for(p = a; p < a+SIZE; ++p) { /*初始化数组全是TRUE*/
*p = TRUE;
}
a[0] = a[1] = FALSE; /*设置前面两个不是质数的数的状态为FALSE*/
i = 2;
for(p = a; p < a+SIZE; ++p) {
while(i < SIZE) { /*找到下一个质数*/
if(a[i++] == TRUE) {
j = i-1;
break;
}
}
for(k = 2; j*k < SIZE && i < SIZE; ++k) { /*处理质数的倍数*/
a[j*k] = FALSE;
}
}
for(p = a; p < a+SIZE; ++p) { /*打印出质数*/
if(*p == TRUE) {
printf("%8d", p-a);
}
}
printf("
");
return 0;
}