题目描述

小技巧：

1、找到大于等于l整除p的最小值 ：ceil(1.0 * l / p)

2、利用1~sqrt(n)中的质数：筛任意l~r(1 <= r <= n)中的合数

分析过程：

1、来看下数据范围[L，R] (L≤R≤2147483647,R-L≤1000000)

2、题目要我们筛出L-R范围内的素数,那么我们只要将这个区间中的合数踢出去不就结束了吗w

3、说起判断合数,合数的一个性质:可以分解为两个不为1且不等于本身的因子相乘 即 n=a*b(n为合数).下证之:

设a<=b 则a * a<a*b

又因a b=n,则a a<=n*n

即a<= sqrt(n)

所以,我们只需要在1-sqrt(n)范围中筛出所有的质数,

然后用我们已经筛出来的因子去在L-R的范围中求出所有的合数,剩下来的即为我们要找的质数,

而R的最大值大约为20亿,所以我们只用求(1-50000中的质数就可以拿他们来玩耍使用了!)

4、流程如下：

筛出1-50000中的所有质数,并且对合数打上标记.

在L-R的范围呢用我们已求出的质数筛出其中的合数(设p为质数,则i*p一定不为质数),并对其打上标记

遍历L-R,没有打标记的元素即为我们所求的素数

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long LL;
LL l, r, cnt;
const int N = 1e6 + 10;
bool st[N];
LL primes[N];
void get_prime(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    cin >> l >> r;
    //找到1~sqrt(n)质数 
    l = l == 1 ? 2 : l; 
    get_prime(N);
    //通过找到的质数筛l ~ r 中的合数
    memset(st, false, sizeof st);
    for (int i = 0; primes[i] * primes[i] <= r; i ++ )
    {
        int p = primes[i];
        LL start = max((((LL)ceil(double (l) / double(p)))* p), (LL) 2 * p);//大于等于l整除p的最小值 
        for (LL j = start; j <= r; j += p)
            st[j - l] = true;   
    } 

    int res = 0;
    for (int i = 0; i <= r - l; i ++ )
        if (!st[i]) res ++;
    cout << res << endl;
    return 0;
}