C.这是一道告诉了你答案的题

题目描述:

由于这题是“一道告诉了你答案的题”，所以题面很清水。给出一个数n，求出1-n中有多少个质数。

         初步思想：对于1-n批量判素数，由当前已知素数筛去后面的是该素数倍数的合数，以此剩下质数。代码大概长这样：

int n;
const int sz=1e7+5;
bool h[sz]={0};//h[i]=0表示i是质数，反之不是
int z[sz],len;//z用于储存已知素数,len表示已知素数的个数
h[1]=1;
for(int i=2;i<=n;i++){
    if(h[i]==0)z[++len]=i;
    for(int j=1;j<=len&&z[j]*i<=n;j++)h[z[j]*i]=1;
}

但是这样的算法效率不高。因为一个合数会被不同质数筛很多次。那么怎么办呢？让一个合数只被它最小的质因数筛掉就可以了。我们的原算法是枚举质数z[j]和它的倍数i，只要让z[j]不大于i中所有质数即可。

输入格式:

一个正整数n。

输出格式:

1~n中的质数个数。

样例输入:

样例输入1：
10
样例输入2：
1

样例输出:

样例输出1：
4
样例输出2：
0

提示:

对于30%的数据 1<=n<=100,000

对于100%的数据 1<=n<=10,000,000

(时限是450ms 如果你写最普通的质数判断也有30分。如果你照着原代码打大概有50分及以上。出题人是不是超善良XD)

 

本题是线性筛法的模板题

感谢叶懿芯

时间限制: 450ms
空间限制: 256MB

---

来源: 2018新生欢乐赛div1