现在的位置: 首页 > 综合 > 正文

短小精悍的线性时间素数筛法

2018年04月24日 ⁄ 综合 ⁄ 共 1587字 ⁄ 字号 评论关闭

 这里是原文:http://blog.csdn.net/mysword/article/details/5122855

我一直以为是O(n)的素数筛法原来是接近O(nlogn)的……真是

我一直是这样写的:
void shai()
{
bool mark[maxn+1]={1};
for (int i=2;i<=maxn;i++)
 if(mark[i])
 {
  prime[++len]=i;
  for (int j=2;j<=maxn/i;j++)
   mark[j*i]=0;
 }
}

输入n,求n以内的所有素数

算法用两个数组存储数据:
一个是prime[],存储n以内所有的素数,其index为pi,初值为0
一个是is_prime[i],表示自然数i(i<=n)是不是质数。
算法如下:
linear_prime_sieves
1:  set is_prime[] to true
2:  for i=2 to n
3:    if is_prime[i]=true then prime[pi++]=i
4:    for j=0 to pi-1
5:      if prime[j]*i>n then exit loop_j
6:      is_prime[prime[j]*i]=false
7:      if i mod prime[j]=0 then exit loop_j
8:    endif
9:  endif

    这个算法有两层循环,第一层遍历2到n之间的所有自然数i,看看它是不是质数,如果是,则把i放进prime数组中。第二层循环是对所有未来的数进行筛选。对于当前正在处理的i,显然它乘以任何一个已经找到的素数的结果肯定是和数,它们将会被剔除。整个算法最核心的一句是第7行:当i可以被某个已经找到的质数整除的时候,循环退出,不再进行剔除工作。这样做的原因是:当prime[j]是i的因子的时候,设i=prime[j]*k,首先,我们可以肯定的说,prime[j]是i的最小质因数,这是因为第二层循环是从小到大遍历素数的;其次,我们可以肯定的说,i已经无需再去剔除prime[j']*i
(j'>j) 形式的和数了,这是因为,prime[j']*i可以写成prime[j']*(prime[j]*k)=prime[j]*(prime[j']*k),也就是说所有的prime[j']*i将会被将来的某个i'=prime[j']*k剔除掉,当前的i已经不需要了。
    然后我们再看看时间复杂度。虽然有两层循环,但是我们发现,正因为有了第7句,所有is_prime数组里面的所有false都只被赋值了一次,而且是在发现它的最小质因数的时候被赋值的。在外层循环执行了O(n)次操作的同时,内层循环里面总的操作次数也是O(n)次。因此,总的时间复杂度是O(n)。因为用了is_prime数组,空间复杂度也为O(n)。
    有了这个算法,我们还能很容易地知道一些信息。先把每个自然数表示成素数幂的形式:i=p1^n1*p2^n2*...*pk^nk,其中p1,p2...pk为自然数i的所有质因数,n1,n2...nk表示每个质因数的个数。由于算法中每个和数都是在发现它的最小质因数的时候找到的,我们能够很容易的知道每个数的最小质因数、最小质因数的个数、以及不重复的质因数个数。
    这个算法给我的感觉是相当的短小精悍。这已经是上个世纪80年代的作品了。reference如下:"P. Pritchard. Linear prime-number sieves: A family tree. Science of Computer Programming, 9:17-35, 1987"。当然,它也是有缺点的,最大的问题就在于空间复杂度为O(n),占用了过多的空间。虽然可以用bit操作把is_prime数组缩小32倍,但是如果那样的话,上面提到的那些附加信息,如每个数的最小质因数,就没法得到了。

抱歉!评论已关闭.