线性筛法求素数的原理与实现

1、何为线性筛法，顾名思义，就是在线性时间内也就是O n用筛选的方法把素数找出来的一种算法，没用过线性筛素数法的人可能会奇怪， 用遍历取余判定素数不是也是线性时 间的吗，没错，但是确切的说线性筛法并不是判定素数的， 而是在线性时间内求出一个素数 表，需要判定是否是素数的时候只要看该数是否在表内就可以瞬间知道是不是素数。比方想求 10000 以内的素数，定义表 int a10000，进行线性筛选后，an的值就代表 n 是不 是素数，an如果是 1,就代表 n 是素数，an如果是 0,就代表 n 不是素数，这就是查表。再判定其他的素数也是一样，不用再做任何计算。而如果用遍历取余，那么每判定一个数都要从

2、头开始再遍历一遍，而线性筛法只在开始一次性运算完，以后只要查表即可， 查表通常只需要 1 条语句。所以如果你的程序从始至终只需 要判定那么几次素数那么用遍历取余即可，但是如果需要屡次判定素数，而且这个数还不是很小的话，那么线性筛法就会表达出巨大的优越性来。线性筛法的核心原理就是一句话：每个合数必有一个最大因子不包括它本身，用这个因子把合数筛掉，还有另一种说法每个合数必有一个最小素因子，用这个因子筛掉合数，其实都一样，但是我觉得这种方法不太容易说明，这种方法我会在最后给出简略说明。这个很容易证明：这个小学就知道合数一定有因子，既然是几个数，就一定有最大的一个。最大因子是唯一的，所以合数只会被它自

3、己唯一的因子筛掉一次，把所有合数筛掉后剩下的就全是素数了。先假设一个数 i，一个合数 t, i 是 t 最大的因数，t 显然可能并不唯一例如 30 和 45 的最大 因数都是 15。那么如何通过 i 知道 t 呢，t 必然等于 i 乘以一个比 i 小的素数。先来说这个 数为什么一定要比 i 小，这很显然，如果是 i 乘上一个比它大的素数，那么i 显然不能是 t最大的因子。再来说为什么要是素数，因为如果乘上一个合数，我们知道合数一定可以被分解成几个素数相乘的结果，如果乘上的这个合数x=p1*p2*，那么t = i * x = i * p1 * p2很显然 p1* i 也是一个因数，而且大于 i。

4、所以必须乘上一个素数。比 i 小的素数一定有不少，那么该乘哪一个呢，既然t 不唯一，那么是不是都乘一遍呢？很显然不行，虽然 t 不唯一，但全乘一遍很显然筛掉的数的数量远远超过合数的数量。我们先 给出结论：任意一个数 i = p1*p2* .*pn , p1、p2、.pn 都是素数，p1 是其中最小的素数，设 T 为 i * M 的积显然 T 就成了一个合数，也就是 T = i * M , M 是素数，并且 Mp1 ,显然M*p2*.pn 要大于 i=p1*p2* .pn, M*p2* .pn 又很显然是 y 的一个因数，那么 y 的最大因数就不是 io 由此说明了了上面给出的结论。本文给出的证

5、明方法并不是很严格，很不严密，但是本文只是想解释线性筛素数的算法，并不是想严格证明，如果想看严格证明请看数论中的证明。另上面提到的线性筛素数的另一种说法，其实到这里读者应该差不多明白了，任何一个合数都可分解为一个素数和另一个数(不一定是素数还是合数)的乘积。我们既然找到了这个合数最大的因数，那么根据上面结论里另一个乘上的素数必然就是他的最小素因数。另一种说法只不过是换一个说法罢了。最后我们就可以得出结论：对于每一个数 i,乘上小于等于 i 的最小素因数的素数，就得到以 i 为最大因数的合数。设有一个数t,只要将所有以比 t 小的数为最大因数的合数筛去，那么比 t 小的数里剩下的就只有素数了。这

6、就是线性筛法求素数的方法。用 c+实现线性筛 10000 以内素数cpp view plaincopy1./author : bjr2.#define N 100003.int flagN+1,primeN+1,pnum;4./*5.flagn表示n是否是素数，1是素数，0不是6.prime中是所有的素数按从小到大排列、7.pnum表示素数的个数8.*/9.void CreatePrime()10.pnum=0; /初始化没有素数11./先将所有数看做素数，然后开始筛选12.for ( inti=0; i=N;i+)13.flagi=1;14.15./遍历筛去所有最大因数是i的合数16.for ( inti=2; i=N;i+)17.if (flagi=1)18./把素数记录下来19.ppnum+=i;20.21./遍历素数表中比i的最小素因数小的素数，并筛去合数22.for