素数密度
题目描述
给定区间 \([L,R]\)（\(1\leq L\leq R < 2^{31}\)，\(R-L\leq 10^6\)），请计算区间中素数的个数。
输入格式
第一行，两个正整数 \(L\) 和 \(R\)。
输出格式
一行，一个整数，表示区间中素数的个数。
样例 #1
样例输入 #1
2 11
样例输出 #1
5
L,R本身太大，不可能直接线性筛\([L,R]\)的素数，但是\(R-L\leq 10^6\)，从这方面入手
R最大为2147483647，我们知道一个定理是说一个合数X的最大质因子p\(\leq\sqrt{x}\)，所以我们可以筛出1~50000的素数，然后根据这些素数用埃氏筛法筛掉\([L,R]\)的合数即可