埃氏筛法

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 const int MAX_N=10005;
 6 
 7 int prime[MAX_N];     //第i个素数 
 8 bool is_prime[MAX_N+1];    //is_Prime[i]为true表示i是素数
 9 
10 int sieve(int n)
11 {
12     int p=0;
13     for(int i = 0; i <= n; i++) is_prime[i]=true;
14     is_prime[0]=is_prime[1]=false;
15     for(int i = 2; i <= n; i++)
16     {
17         if(is_prime[i])
18         {
19             prime[p++]=i;
20             for(int j = 2*i; j <= n; j+=i) is_prime[j]=false;
21         }
22     }
23     return p;
24 }
25 
26 int main()
27 {
28     //请输入你要筛选的范围
29     int m;
30     cin>>m;
31     int q=sieve(m);
32     cout<<q<<endl;   //输出在m下边的素数的个数（包括m） 
33 }