在用“筛法”求素数时，每次筛除素数的动作，其实有很多是重复的！比如，如果一个数是3*5*7*9，那么删除的时候，它会被作为3的倍数，5的倍数，7的倍数，9的倍数，被重复判断删除4次。类似的，较大的数有较多的因数，那么，删除它所耗费的时间会很多！如何来优化“筛法”的算法，使之不重复呢？
思路如下：从2开始，先删除2²，2³，2³，···，接着删除2·3，2²·3，2³·3，···，而此时并不删除3。再删除2·5，2²·5，2³·5，···，接下来2·7，2²·7，2³·7，···。一般而言，当发现p是一个素数时，先删除p²，p³，p³，···这一系列合数。因为p是素数，所以p²，p³，p³，···不可能被其它数整除。接着，找出比p大，但是第一个没有被删除的数q。再删除p·q，p²·q，p³·q，···。因为p是素数，q为目前为止未删除。所以p^¡·q之前也没有被删除。
证明上面这点很重要。如果p^i·q之前已经被删除的话，那么依照上面讲的法则。一定有一个小于p的素数a，使得存在a^k·b=p^i·q，这样，删除a的倍数时，会把p^i·q删除掉。不过，a^k·b=p^i·q并且a<p这是不可能的！因为a与p都为素数，它们之间无法互相整除。为满足等式，必须有p^i整除q，即q=a^k·(b/q^i)。这样以来，q便是a的倍数了！在删除a的倍数时，q已经被删除！与q是大于p的未被删除的性质矛盾！
根据上面的证明，线性筛法所做的操作不会重复！因为求小于n的素数时，p最大不会超过√n，所以p^2< =n。同样，对于任意p^i·q也必须限定在n的范围以内。
#include <stdlib .h>
#define MAXSIZE 1000
#define NEXT(x) x = next[x]
#define REMOVE(x) { next[previous[x]] = next[x]; \
previous[next[x]] = previous[x]; \
}
#define INITIAL(n) { unsigned long i; \
for (i = 2; i < = n; i++) \
previous[i] = i-1, next[i] = i+1;\
previous[2] = next[n] = NULL; \
}
void main(void)
{
unsigned long previous[MAXSIZE+1]; // 指向前数
unsigned long next[MAXSIZE+1]; // 指向后数
unsigned long prime, fact, i, mult;
unsigned long n;
unsigned long count = 0;
char line[100], dummy;
printf("\n线性筛法求素数");
printf("\n====================");
printf("\n\n求出2到n之间的素数，输入n --> ");
gets(line);
n = strtoul(line, &dummy, 10);
INITIAL(n); // 初始化序列
for (prime = 2; prime*prime < = n; NEXT(prime))
for (fact = prime; prime*fact <= n; NEXT(fact))
for (mult = prime*fact; mult <= n; mult *= prime)
REMOVE(mult); // 删除p^i·q
for (i = 2; i != NULL; NEXT(i)) {
if (count % 8 == 0) printf("\n");
printf("%6ld", i);
count++;
}
printf("\n\n2到n之间的素数共有%d个", count);
}
如果不仔细琢磨这个程序，确实很难看懂！程序使用了3个循环来实现删除的操作。并将初始化，删除，移位的操作定义为简短的宏定义。如果实在看不懂的话，可以拿出笔来，简单的走一遍程序。弄清楚，删除以及移动目标是如何实现的！细细体会previous和next数组的作用，以及删除的实现！
比如，previous[3],previous[4],previous[5]分别为2，3，4。next[2], next[3], next[4], next[5]的值分别为3，4，5，6。再每一轮删除之后，每个previous[i]和next[i]数组中的元素将会指出i之前与之后的最近的未被删除的素数！REMOVE(4)之后，previous[5]=previous[4]=3，next[3] = next[4] = 5。换句话说，就是4被删除了，5的前面一位此时指向3，3的后面一位指向5。
真的是非常巧妙啊！Kada的笔记中贴出的代码，有些都是20年前的计算机学家或者数学家，以及专业的人士发表在相关杂志的！若非几十年的锤炼，实在难以精尖！
看看线性筛法