素数密度_NOI导刊2011提高（04）

时间：2023-03-09 16:31:02
素数密度_NOI导刊2011提高（04）

题目描述

给定区间[L, R](L <= R <= 2147483647，R-L <= 1000000)，请计算区间中素数的个数。

输入

两个数 L 和 R。

输出

一行，区间中素数的个数。

样例输入

2 11
样例输出
5
 
可以发现R - L范围很小，但L和R很大，用普通的筛法时空间都会超。
但可以转换思路，只筛L ~ R的素数。
此前先筛出2-√r的素数，只有大约47000个
将这些素数在L ~ R里的倍数筛掉，注意别把素数本身筛掉
比如样例：2~11，会把2，3筛掉。如果没有注意的话小数据会过不了（大的可以过，亲测只有样例不行）
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

long long l,r;

int k;

int prime[];

int vis[];

int ans;

int main()

{long long i,j,p;

    cin>>l>>r;

     for (i=;i<=sqrt(sqrt(r));i++)

     if (vis[i]==)

     {

          for (j=i*i;j<=sqrt(r);j+=i)

           vis[j]=;

     }

      for (i=;i<=sqrt(r);i++)

       if (vis[i]==)

       {

           k++;

           prime[k]=i;

       }

       memset(vis,,sizeof(vis));

    for (i=;i<=k;i++)

     {

         int x=(int)(l/prime[i]+0.5);

         for (j=x*prime[i];j<=r;j+=prime[i])

         if (j%prime[i]==&&j/prime[i]>)

           vis[j-l]=;

     }

     for (i=l;i<=r;i++)

      if (vis[i-l]==)

       {//cout<<i<<endl;

        ans++;

       }

    cout<<ans;

}

相关文章