[luoguP1835] 素数密度_NOI导刊2011提高（04）（素数筛）

传送门

数据辣么大，怎么搞？（L≤R≤2147483647）

注意到RL≤1000000

所以可以直接筛RL区间内的数，

但是需要用已知的小的素数筛，

RL区间内的大部分数肯定能用较小的素数筛去，但是还有一些较大的数，可能等于两个大质数的乘积，没法被筛去。

但是又注意到，数据最大才10位，也就是说我们只需要用位数<=5的素数筛就可以了，所以先预处理出来，直接筛就ok了。

#include <cstdio> #define N 1000001 #define max(x, y) ((x) > (y) ? (x) : (y)) int L, R, cnt, ans; int prime[N]; bool notprime[N], ansprime[N]; int main() for(i = 1; i <= cnt; i++) for(j = max(2, L / prime[i]); j <= R / prime[i]; j++) ansprime[j * prime[i] L] = 1; for(i = 0; i <= R L; i++) if(!ansprime[i]) ans++; printf("%d\n", ans); return 0; }

　　

上一篇：[luoguP1360] [USACO07MAR]黄金阵容均衡Gold Balanced L…

下一篇：[POJ2443]Set Operation（bitset）

---

数论 素数筛