线性筛法找素数_sundowner_新浪博客

求0-N之间额素数，线性筛法是我见过的最好的算法了，具有线性时间复杂度。

现将算法思想描述如下。

说明：解决这个问题的诀窍是如何安排删除的次序，使得每一个非质数都只被删除一次。

      中学时学过一个因式分解定理，他说任何一个非质（合）数都可以分解成质数的连乘积。例如，16=pow(2,4)，18=2*pow(3,2)，691488=pow(2,5)*pow(3,2)*pow(7,4)等。如果把因式分解中最小质数写在最左边，有16=pow(2,4)，18=2*9,691488=pow(2,5)*21609,；换句话说，把合数N写成N=pow(p,k)*q，此时q当然是大于p的，因为p是因式分解中最小的质数。由于因式分解的唯一性，任何一个合数N，写成N=pow(p,k)*q的方式也是唯一的。

由于q>=p的关系，因此在删除非质数时，如果已知p是质数，可以先删除pow(p,1),pow(p,2),pow(p,3)…，接着找出比p大而没有被删除的数q，然后删除pow(p,1)q,pow(p,2)q,pow(p,3)q，…，一直到pq>N为止。

因为每个非质数都只被删除一次，可想而知，这个程序的速度一定相当快。依据Gries与Misra的文章，线性的时间，也就是与N成正比的时间久足够了（此时要找出2N的质数）。

Read full article from 线性筛法找素数_sundowner_新浪博客