#include<iostream>  
#include<math.h>  
#include<stdlib.h>

using namespace std;  
const int MAXV = 100; //素数表范围  
bool flag[MAXV+1]; //标志一个数是否为素数  
int prime[MAXV+1]; //素数表,下标从0开始  
int size=0; //素数个数  

void genPrime(int max)  
{  
    memset(flag, true, sizeof(flag));//首先对标签数组进行初始化，全部设为true。  
    for(int i = 2; i <= max / 2; i++)  
    {  
        /* 
        从2开始，删除2的倍数 
        */  
        if(flag[i])  
        {  
            //j=i<<1等价于 j=i*2，即j是i的两倍，而最后的j+=i，则表示下一个循环j是i的3倍，接着4倍。。。
            //i的所有2~N倍数肯定都不是素数，因此将flag置为0，直到最后一位。
            for(int j = i << 1 ; j <= max; j += i)
            {  
                flag[j] = false;  
            }  
        }  
    }  
    for(int i = 2 ; i <= max; i++)  
    {  
        if(flag[i])  
        {  
            prime[size++] = i;//存储素数。将所有标志位依然为1的标志写入素数数组中去。  
        }  
    }  
}  

void genPrime2(int max)  
{  
    memset(flag, true, sizeof(flag));//首先对标签数组进行初始化，全部设为true。  
    int sq=sqrt((double)max)+1;  //一个数 n 如果是合数，那么它的所有的因子不超过sqrt(n)
    int i,j, k;  
    for(i = 2;i<=sq; i++)  
    {  
        if(flag[i])  
            for(j=2,k=max/i+1;j<k;j++)  
                flag[i*j] = false; //所有i的j倍都不是素数 
    }  
    for( i = 2 ; i <= max; i++)  
    {  
        if(flag[i])  
        {  
            prime[size++] = i;//存储素数。将所有标志位依然为1的标志写入素数数组中去。  
        }  
    }  
} 
 
int main()  
{  
//  genPrime(MAXV);  
    genPrime2(MAXV);  
    //输出所有素数。  
    for(int i=0;i<size;i++)  
        cout<<prime[i]<<" ";
    cout<<endl;
    system("pause");
    return 0;  
}  
/*
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
请按任意键继续. . .
*/

快速线性筛法

快速线性筛法没有冗余，不会重复筛除一个数，所以“几乎”是线性的。

#include<iostream>
using namespace std; 
   
const long N = 200000;   
long prime[N] = {0},num_prime = 0;    
int isNotPrime[N] = {1, 1};   

int main()    
{     
    for(long i = 2 ; i < N ; i ++)       
    {            
        if(! isNotPrime[i])               
             prime[num_prime ++]=i;  
        //关键处1        
        for(long j = 0 ; j < num_prime && i * prime[j] <  N ; j ++)
        {               
             isNotPrime[i * prime[j]] = 1;  
             if( !(i % prime[j] ) )  //关键处2                  
               　　break;           
        }        
    }        
    return 0;   
}  

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。