首页 > 代码库 > 洛谷 P1835 素数密度_NOI导刊2011提高（04）题解
洛谷 P1835 素数密度_NOI导刊2011提高（04）题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：https://www.luogu.org/problem/show?pid=1835
题目描述
给定区间[L，R](L≤R≤2147483647,R-L≤1000000)，请计算区间中素数的个数。
输入输出格式
输入格式：两个数L和R。
输出格式：一行，区间中素数的个数。
输入输出样例
输入样例#1：
2 11
输出样例#1：
5
分析：裸的区间素数筛。
代码中有详细注释（其中区间素数筛函数大部分借用了《挑战程序设计》）
不过是原文中代码是筛选[l,r)，此题要求闭区间，所以把所有的<都改为≤。
AC代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 const int MAXA = 1000010; 7 const int MAXB = 1000010; 8 typedef long long ll;//简记 9 bool is_prime[MAXA];//偏移区间，大小为l 10 bool is_prime_small[MAXB];//用于筛选偏移区间的区间，大小为√r 11 12 13 //对区间[l,r]内的整数执行筛法。is_prime[i-l] = true则i是素数14 void segment_sieve(ll l,ll r)//区间筛 15 {16 for(int i = 0;(ll) i * i <= r;i ++) 17 is_prime_small[i] = true;18 //处理[0,√r] 其中√r是区间[l,r]中任意数的最大因子 19 for(int i = 0;i <= r - l;i ++)20 is_prime[i] = true;//将区间[l,r]向左偏移a，变为[0,r-l] 21 //以上 将区间内所有需要处理的数表预设为true 22 for(int i = 2;(ll)i * i <= r;i ++)23 {24 if(is_prime_small[i])//若i是素数 25 {26 for(int j = 2*i; (ll) j*j <= r;j += i)//j是i的倍数 27 is_prime_small[j] = false;//根据i，筛[2,√r]28 for(ll j = max(2LL,(l+i-1)/i)*i;j <= r;j += i)29 //给j赋值的语句相当于 【ll j = l/i * i ; if(j < l) j + l;】 30 is_prime[j-l] = false;//筛[l,r] ,偏移存储 31 }32 }33 //如果主函数中输出素数值，只需将下标+a即可. 34 } 35 36 int main()37 {38 int l,r;39 int ans = 0;40 scanf("%d%d",&l,&r);41 segment_sieve(l,r);42 for(int i = 0;i <= r-l;i ++)43 {44 if(is_prime[i])45 ans ++;46 }47 printf("%d",ans);48 return 0;49 }
洛谷 P1835 素数密度_NOI导刊2011提高（04）题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。