快速线性筛法求素数

更新于: | 阅读次数: | 评论数:
字数统计: 1.2k | 阅读时长 ≈ 5

筛法求素数

基本步骤

说到求素数，其实在刚开始学C++的时候就已经见过诸如此类的问题，不过现在最常见的还是筛法求素数

谈及筛法求素数，其大致思路可分为如下五步：

  1. 把2到n的自然数放入a[2]到a[n]中(所放入的数与下标号相同) ;
  2. 在数组元素中以下标为序，按顺序找到未曾找过的最小素数minp和它的位置p(即下标号);
  3. 从p+1开始，把凡是能被minp整除的各元素值从a数组中划去(筛掉)，也就是把该元素标记为0;
  4. 让p=p+1，重复执行第(2) (3)步骤，知道，minp>floor(sqrt(n))为止;
  5. 打印输出a数组中留下来的数，未被筛掉的各元素值;

缺陷分析

这种求素数的算法很容易被理解，其时间复杂度介于O(n)~O(n*logn)是一种比较流行的方法。但是同样的，这种算法也存在先天性的缺陷，我们简单分析：

对于一个数30，可分解为30=215=310=5*6，显然，当循环,2,3,5,6,10,15时都会筛除一次30这个数，而当n很大时，就会出现许多的冗余操作，这个算法可以进一步进行优化来使算法的效率提高，因此，一种名为快速线性筛法的算法应运而生。这种算法的智慧之处在于——对于2~n的每一个数，它只筛去到目前为止它能筛到而之后的其他数筛不到的几个合数，而把它能筛到，另有别的数也能筛到的数留个接下来的数去筛，这样的话就能使得素数的筛选不重不漏——说起来容易做起来难，这样的算法应该如何实现呢？

快速线性筛法求素数

基本步骤

对于快速筛法求素数，其步骤也可分为如下几个阶段：

  1. 开一个n+1大小的数组num[n]来存放每一个元素的筛留情况(即对于num[n]的每个数与下标号相同，对于任意num[n]有num[n]=0,num[n]=1两种情况，如果num[n]=0则是素数，反之num[n]=1时是合数);

  2. 再开一个数组prime[n]来存放筛出的素数以便最后输出结果;

  3. 对于一个数k,总是进行从n*prime[0]~n*prime[j](由小到大来乘)，直到if(n%prime[j]==0)成立时break掉

    这是这个算法的精髓所在，所以弄清楚原因是十分必要的！！！
    对于一个数c=a*b(b为c的最小质因数），当通过该算法的循环循环至c*b时，易得此时c%b==0,如果此时继续循环至b后面的一个素数d，则有：c*d=a*b*d=(a*d)*b，因为d>b,所以a*d>c。当循环从c继续查找到a*d时我们发现当a*d再次与素数b想乘时，就又对cd进行了一次操作，出现了冗余，所以在if(n%prime[j]==0)成立时要将该层循环break掉；
    举个例子，对于一个数9，9\    2=18将18标记为合数，循环继续；9\3=27将27标记为合数，此时发现9%3=0，循环退出。如果将循环继续下去会出现筛除9\5=45的情况，而45=15*3，在15时会被在筛去一次，故不可行

  4. 完成了算法中最重要的一步，最后只要将存放筛出的prime[]数组中的素数即可！

这种算法的写法也十分简单，这里只给出一种与普通筛法求素数比较程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cmath>
#define inf 20000005
using namespace std;
int n;
bool a[inf+1];
long num[inf+1]={1,1},prime[inf+1]={0},number=0;                                                      

void putongshaifa()                          
{
	clock_t begin,end;                                            
	begin=clock();
	for(int i=0;i<=n;++i)
	  a[i]=true;
	a[1]=false;
	for(int i=2;i<sqrt(n);++i)
	  if(a[i])
	    for(int j=2;j<=n/i;++j)
	      a[i*j]=false;
	end=clock();
	/*for(int i=2,t=0;i<=n;++i)
	  if(a[i])
	  {
	  	cout<<i<<" ";
	  	++t;
	  	if(t%10==0) cout<<endl;
	  }
	cout<<endl;*/
	printf("普通筛法-Time used:%d ms\n",end-begin); 
	return;
}


void kuaisushaifa()                 
{
	clock_t begin,end;                                             
	begin=clock();
	for(int i=2;i<=n;++i) 
	{
		if(!num[i])
		  prime[number++]=i;
		for(int j=0;j<number && i*prime[j]<=n;j++)  
        {  
            num[i*prime[j]]=1;                 
            if(!(i%prime[j]))             
                break;  
        }  
    }
	end=clock();
    /*for(int i=0;i<number;i++)
    {  
        if(i%10==0) printf("\n");  
        printf("%3d",prime[i]);  
    }  */
	printf("快速筛法-Time used:%d ms\n",end-begin); 
	return;
}

int main()
{
	//freopen("prime.txt","w",stdout);
	scanf("%d",&n);
	int _test=10;
	while(_test--)
	{
		putongshaifa();
		kuaisushaifa();
		cout<<endl;
	}
    return 0;   
}
-------------本文结束感谢您的阅读-------------