素数筛

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 using namespace std;
10 #define ll long long
11 const int inf=99999999;
12 const int mod=1e9+7;
13 const int maxn=1e7+1;
14 //判断素数函数
15 bool isprime(int num)//处理较大数据时，用此函数预处理比较慢，用不上 
16 {                    
17     if(num==0||num==1)
18         return false;
19     int j=(int)sqrt(num);
20     for(int i=2;i<=j;i++)
21         if(num%i==0)
22             return false;
23         return true;
24  } 
25 int pre[maxn];//预处理数组 
26 int main()
27 {
28 //    memset(pre,0,sizeof(pre));
29     //素数预处理
30     //pre数组为0时为素数 
31     pre[0]=pre[1]=1;
32     //特判0和1 
33     
34     for(int i=2;i*i<=maxn;i++)
35     {
36         if(!pre[i])//已经为1不是素数就跳过 
37         {
38             for(int j=i+i;j<=maxn;j+=i)//每一轮筛去例如2的倍数，3的倍数，等等 
39             {
40                 pre[j]=1;
41               // printf("%d ",j);测试的话把可以maxn改小，然后观察每次筛掉的数 
42             }
43            // printf("
");
44         }
45     }
46 //     printf("
");
47     for(int i=0;i<1000;i++)
48     {
49         if(!pre[i])
50             printf("%d ",i);
51      } 
52     
53     return 0;
54 }
大佬见笑，，