小于等于n的素数的个数（埃式筛选法和欧拉筛选）

问题描述

给定数字n，求出小于等于n的素数的个数，假设n<=1000000

思路

找出数字n之前的所有素数，用数组isprime[i]表示i是否是素数；用num[i]表示小于等于数字i的素数有多少。 那么最重要的就是解决判断一个数是否是素数

方法1

最基础的方法是对每个数从2开始遍历到根号n，判断有没有n的因子，但是显然效率非常低

方法2

埃式筛选法（ Eratosthenes筛选）预处理一下 原理：一个合数总是可以分解成若干质数的乘积 初始化isprime数组为1，遍历所有小于题目给定的1000000的数，从1开始判断，如果改数不是素数，那么就将其isprime改成0. 显然1不是素数，num[1]=0；从2开始，如果一个数i是素数（比如2），那么这个数的倍数都不是素数（也就是，4,6,8,10…）这些数至少有一个素数因子了，因此将i的所有倍数的isprime都设为0，而num[i]=num[i-1]+1;

如果一个数i不是素数，那么不用处理，直接num[i]=num[i-1]

代码如下

const int cont = 1000002;
bool isprime[1000002];
int num[1000002];
int main()
{
    int n;
    memset(isprime,1,sizeof(isprime));
    memset(num,0,sizeof(num));
    isprime[1]=0;
    num[1]=0;
    for(int i = 2;i<cont;i++)
    {
        if(isprime[i])//是素数
        {
            num[i]=num[i-1]+1;
            for(int j = 2*i;j<cont;j+=i)//去掉所有倍数
                isprime[j]=0;
        }
        else
            num[i]=num[i-1];
    }
    while(~scanf("%d",&n))
    {
        printf("%d
",num[n]);
    }
}

分析： 时间复杂度是O(nloglogn) 效率已经比较高，但是做了一些无用功，一个数会被重复筛选很多遍， 比如2和3的倍数中都有6

方法2

欧拉筛选 欧拉筛选的目的就是要不做重复功，筛选过的不再重复筛选，这里的prime[i]=k表示的是第i个素数是k；第一重循环是找素数，第二重还是借助找到的素数去除该数的倍数，只不过去除的方式不同 代码如下：

const int cont = 1000002;;  
int Prime[cont];  
bool vis[cont];  
void prepare()  
{  
    int num = 0;  
    memset(vis,true,sizeof(vis));  
    for(int i = 2; i <= cont; ++i)  
    {  
        if(vis[i])  
            Prime[++num] = i;  
        for(int j = 1; j <= num; ++j)  
        {  
            if (i * Prime[j] > cont)  
                break;  
            vis[i * Prime[j]] = false;  
            if (i % Prime[j] == 0) //表明这个数已经被筛过了 
                break;  
        }  
    }  
}