题解 AT261 【与えられた数より小さい素数の個数について】

数据小，这道题可以用暴力的算法，也可以用更加高级一点的素数筛法

暴力做法已经有了，线性筛的算法有了，这里给出一个简单一点的但比暴力算法快一点的算法：

#include<bits/stdc++.h>
using namespace std;
bool a[10000010];//合数表
int main()
{
　　long long n;
　　scanf("%lld",&n);
　　for(int i=2;i<=n;i++){
　　　　if(a[i])continue;//如果已经在合数表里了，相当于下面动图中有颜色的部分
　　　　for(int j=i;j<=n;j+=i){//如果不满足，就一定是质数
　　　　　　if(a[j])continue;
　　　　　　a[j]=1;//将找到的这个质数的倍数全部上色，即加入合数表
　　　　}
　　　　b[i]=1;
　　}
　　long long ans=0;
　　for(int i=2;i<=n-1;i++){
　　　　if(b[i])ans++;
　　}//统计即可
　　cout<<ans<<endl;
}

就是一个与线性筛极其类似的埃氏算法，可以叫做伪线性筛，它们两个之间是常数关系

这里的意思很简单，通过一个小动图即可了解

在这里用这个代码可以直接过P3383。注意：有一个小地方不同。

Update：2018.3.12//补充完善内容