洛谷P1835素数密度[NOI导刊]
1599+
作者：crxis 发布：2021-07-08 分类：筛法
题目大意：区间[L, R]中有多少个质数？区间大小不超过100万，L、R在int范围。
题目描述
给定区间 $[L,R]$（$1\leq L\leq R < 2^{31}$，$R-L\leq 10^6$），请计算区间中素数的个数。
输入输出格式
输入格式
第一行，两个正整数 $L$ 和 $R$。
输出格式
一行，一个整数，表示区间中素数的个数。
输入输出样例
输入样例 #1
2 11输出样例 #1
5解题思路
一个合数n，总会有一个质因子，不超过$\sqrt{n}$，我们可以筛出int开根号内的所有质数，然后用他们去筛合数，剩下的就是质数。
虽然区间[L, R]很大，但L之前和R之后都不需要筛，如L=100000，R=500000，质数2如果从4开始筛，那么4~99998都是白做的，我们可以从L/2倍开始，每次增加2，这样每个质数p只需要循环(R-L)/p次即可，时间复杂度就是O(nlogn)。
注意，质数翻倍过程中，需要筛的是[L, R]内的，0倍和1倍需要过滤掉。
程序实现
