题解 P1835 【素数密度_NOI导刊2011提高（04）】

1124828077ccj · 2016-07-30 13:02:44 · 题解

看这里，最简单的代码！！！用最普通的筛法（代码有注释）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cstdlib>
using namespace std;
int a,b,f[1000002],ans,y,c;
int main()
{
    scanf("%d%d",&a,&b);int u=sqrt(b);if (u<2)u=2;
    for (int i=2;i<=u;i++)
    {
        c=b/i;//算出最大能乘多少
        for (int j=c;j>=2;j--)
        {y=j*i;if (y<a)break;else f[y-a]=1;}//如果发现接下来筛掉的书比a要小那就不用筛了，否则让这个数减去a得到的结果就是0-1000000之间的数字
    }
    for (long long i=a;i<=b;i++)//记住，一定要longlong，否则当b等于int最大值时，i再加一就会爆掉（因为这个我错了好久）
    {if (!f[i-a])ans++;}
    printf("%d",ans);
    return 0;
}