素数筛法求素数

素数筛类似于打表标记，预先处理掉非素数的数，即素数的倍数（任意非素数都可以由几个素数相乘得到），于是效率比暴力求解快得多。

埃氏筛法的效率为O(n loglog n)，简单易懂，但是会重复标记，比如当i为2时，6会被标记掉，然而当i为3时，6又会被重复标记，这样的重复访问加大了时间复杂度，于是有了欧拉筛。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<ctime> 
 5 using namespace std;
 6 bool v[100000055];
 7 void ss(int n)
 8 {
 9     memset(v,true,sizeof(v));//全定为素数 
10     for(int i=2;i<=sqrt(n);i++)
11     {
12         if(v[i])
13         {
14             for(int j=i*i;j<=n;j+=i)//筛掉i的倍数 
15             v[j]=0;
16         }
17     }
18 }
19 int main()
20 {
21      clock_t start,finish;
22    double totaltime;
23    
24     int n;
25     cin>>n;
26     start=clock();
27     ss(n);
28     int ans=0;
29     for(int i=2;i<=n;i++)
30     {
31         if(v[i])
32         ans++;
33     }
34     cout<<ans<<endl;
35       finish=clock();
36    totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
37    cout<<"
此程序的运行时间为"<<totaltime<<"秒！"<<endl;
38    return 0;
39 }

欧拉筛的时间复杂度为o(n)，就是线性。注释为本人拙见，水平有限见谅。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int v[10000000],f[10000000];
 5 int ss(int n)
 6 {
 7     memset(v,0,sizeof(v));//用0表示素数，1表示非素数,先全部标记为素数 
 8     int cnt=0;
 9     for(int i=2;i<n;i++)
10     {
11         if(!v[i])//当这个i为素数时 
12 13             f[cnt++]=i;//存素数 
14             for(int j=0;j<cnt&&i*f[j]<n;j++)
15             {
16                 v[i*f[j]]=1;//筛掉素数i的倍数，任意非质数都可以由质数相乘得到 
17                 if(i%f[j]==0)//当素数i是前几个素数中某个数的倍数时，f[j+1]*i已经被f[j]乘以某个数筛掉了
18                 break;
19             }
20 21     }
22     return cnt;//n以内素数的个数 
23 }
24 int main()
25 {
26     int n;
27     cin>>n;
28     int cnt=ss(n); 
29     for(int i=0;i<cnt;i++)
30     cout<<f[i]<<' ';
31     cout<<endl;
32 }