素数筛模板

求素数是程序设计比赛中经常遇到的问题，最基本的方法是通过素数的定义直接判断，只能被1和它本身整除的数就是素数了。这种方法适合判断单个数是否为素数，当要求一个范围内素数而这个范围又比较大时，这种方法就不太使用了，甚至程序要运行几分钟才能算出结果。

筛法的思想是去除要求范围内所有的合数，剩下的就是素数了，而任何合数都可以表示为素数的乘积，因此如果已知一个数为素数，则它的倍数都为合数。

普通的线性筛法：

 1 #include"cstdio"
 2 #include"cstring"
 3 using namespace std;
 4 #define MAX 100000//求MAX范围内的素数
 5 long long su[MAX],cnt;
 6 bool isprime[MAX];
 7 void prime()
 8 {
 9     cnt=1;
10     memset(isprime,1,sizeof(isprime));//初始化认为所有数都为素数
11     isprime[0]=isprime[1]=0;//0和1不是素数
12     for(long long i=2;i<=MAX;i++)
13     {
14         if(isprime[i])//保存素数
15         {
16             su[cnt++]=i;
17         }
18         for(long long j=i*2;j<=MAX;j+=i)//素数的倍数都为合数
19         {
20             isprime[j]=0;
21         }
22     }
23 }
24 int main()
25 {
26     prime();
27     for(long long i=1;i<cnt;i++)
28         printf("%d  ",su[i]);
29     return 0;
30 }

普通的线性筛法虽然大大缩短了求素数的时间，但是实际上还是做了许多重复运算，比如2*3=6，在素数2的时候筛选了一遍，在素数为3时又筛选了一遍。如果只筛选小于等于素数i的素数与i的乘积，既不会造成重复筛选，又不会遗漏。时间复杂度几乎是线性的。

优化后的线性筛法：

 1 #include"cstdio"
 2 #include"cstring"
 3 using namespace std;
 4 #define MAX 100000//求MAX范围内的素数
 5 long long su[MAX],cnt;
 6 bool isprime[MAX];
 7 void prime()
 8 {
 9     cnt=1;
10     memset(isprime,1,sizeof(isprime));//初始化认为所有数都为素数
11     isprime[0]=isprime[1]=0;//0和1不是素数
12     for(long long i=2;i<=MAX;i++)
13     {
14         if(isprime[i])
15             su[cnt++]=i;//保存素数i
16         for(long long j=1;j<cnt&&su[j]*i<MAX;j++)
17         {
18             isprime[su[j]*i]=0;//筛掉小于等于i的素数和i的积构成的合数
19         }
20     }
21 }
22 int main()
23 {
24     prime();
25     for(long long i=1;i<cnt;i++)
26         printf("%d  ",su[i]);
27     return 0;
28 }

输出的结果是这样的：