题解 P1835 【素数密度】

· · 题解

博客食用更佳

刚开始作者有一种naive的想法

CODE:

#include<bits/stdc++.h>
using namespace std;
long long l,r,ans=0;
bool prime(long long n)
{
    if(n==1)
    return false;
    if(n==2)
    return true;
    for(int i=2;i<=sqrt(n);i++)
    if(n%i==0)
    return false;
    return true;
}
int main()
{
    cin>>l>>r;
    for(int i=l;i<=r;i++)
    if(prime(i)==true)
    ans++;
    cout<<ans;
    return 0;
}

亲测

这时作者意识到，LG的绿题是水不过的。

那么就换个方法——素数筛！

求出2~50000的所有素数，\sqrt{2147483647} =46000+

把这些数的倍数删除，剩下的就是素数了

这题的空间给的还是很足的，如果是32MB就要小心数组大小惹

R-L<=1e6,数组完全可以只开1e5

之后对于>1e5的L和R，在存素数时减去L即可

正解CODE

#include<bits/stdc++.h>
using namespace std;
const long long maxn=1e5,temp=1;
long long l,r,ans=temp-1,prime[maxn+5];
bool visit[maxn+5],flag[maxn+5];//visit[i]==1,i不是素数，反之则亦然
//反作弊：这里flag数组开小了10倍，会RE滴
int main()
{

    cin>>l>>r;
    for(int i=temp+1;i<=sqrt(maxn);i++)
    if(!visit[i])
    for(int j=temp+1;j<=maxn/i;j++)
    visit[i*j]=temp;
    for(int i=temp+1;i<=maxn;i++)
    if(!visit[i])
    prime[++prime[temp-1]]=i;
    for(int i=temp;i<=prime[temp-1];i++)
    for(int j=max(l/prime[i],temp);j<=r/prime[i];j++)
    {
        if(j==temp)
        continue;
        if(j*prime[i]<l)
        continue;
        flag[prime[i]*j-l]=1;//平移数组，防止空间爆炸
    }
    for(int i=temp-1;i<=r-l;i++)
    if(!flag[i])
    ans++;
    cout<<ans;
    return temp-1;
}

评测记录