1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4  5 using namespace std; 6  7 int prim[3000000]={2,3,5}; 8 //素数是分为基本素数{2,3}、阳素数{6N+1，N>=1}形式的、阴素数{6N-1，N>=1}形式的 9 //为了代码的好写，在这里这样写的 :10 //数除了{2,3,5}为素数，其他的数可以写成6N，6N+1,6N+2,6N+3,6N+4,6N+5  N>=1 可以表示全部的数11 //6N，6N+2,6N+4都为偶数，不是素数，6N+3 == 3(2N+1) 不是素数，那么就只筛6N+1和6N+5就可以了12 int main()13 {14     int i, j, flag;15     int gcd = 2;16     int k = 3;17 18     for(i=7;i<=20000000;i+=gcd)19     {20         gcd = 6-gcd;//6N+1和6N+5的变换。21         flag = 1;22         for(j=0;prim[j]*prim[j]<=i;j++)//判断一个数是否为素数，只需判断这个数在2--sqrt(x)范围即可。23             if(i%prim[j] == 0){//因为一个开根号比乘法是要慢的，所以用乘法速度更快。24                 flag = 0;25                 break;26             }27         if(flag)//若这个数没有被其他素数整除 说明为素数。28             prim[k++] = i;29     }30     for(i=0;i<k;i++)31         printf("%d  ",prim[i]);32     return 0;33 }

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4  5 using namespace std; 6  7 int hash[2000003]; 8 int prim[500000]; 9 //此为埃氏筛法，是很朴素的一种筛法，O(nlogn)的时间复杂度，可以应付大部分的素数筛，而且代码很短。10 int main()11 {12     int i, j, k = 0;13 14     memset(hash,0,sizeof(hash));15     for(i=2;i<=2000000;i++)16     {17         if( !hash[i]){18             prim[k++] = i;19             for(j=2*i;j<=2000000;j+=i)20                 hash[j] = 1;21         }22     }23     for(i=0;i<k;i++)24         printf("%d ",prim[i]);25     return 0;26 }