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

ysner · 2017-10-01 22:12:53 · 题解

裸的区间素数筛。

代码中有详细注释（其中区间素数筛函数大部分借用了《挑战程序设计》）

不过是原文中代码是筛选[l,r)，此题要求闭区间，所以把所有的<都改为≤。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
bool is_prime[1000005];//偏移区间，大小为l 
bool is_prime_small[1000005];//用于筛选偏移区间的区间，大小为√r  
 //对区间[l,r]内的整数执行筛法。is_prime[i-l] = true则i是素数
 void segment_sieve(ll l,ll r)//区间筛 
 {
     for(int i = 0;(ll) i * i <= r;i ++) 
         is_prime_small[i] = true;
     //处理[0,√r] 其中√r是区间[l,r]中任意数的最大因子 
     for(int i = 0;i <= r - l;i ++)
         is_prime[i] = true;//将区间[l,r]向左偏移a，变为[0,r-l] 
     //以上 将区间内所有需要处理的数表预设为true 
     for(int i = 2;(ll)i * i <= r;i ++)
     {
         if(is_prime_small[i])//若i是素数 
         {
             for(int j = 2*i; (ll) j*j <= r;j += i)//j是i的倍数 
                 is_prime_small[j] = false;//根据i，筛[2,√r]
             for(ll j = max(2LL,(l+i-1)/i)*i;j <= r;j += i)
         //给j赋值的语句相当于 【ll j = l/i * i ; if(j < l) j + l;】 
                  is_prime[j-l] = false;//筛[l,r] ,偏移存储
         }
     }
     //如果主函数中输出素数值，只需将下标+a即可. 
} 
il int gi()
{
    re int x=0;
    re int t=1;
    re char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') t=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
} 
int main()
{
     int l,r;
     int ans = 0;
     l=gi();r=gi();
     segment_sieve(l,r);
     for(int i = 0;i <= r-l;i ++)
     {
         if(is_prime[i])
             ans ++;
     }
     printf("%d\n",ans);
     return 0;
}