1. 题目

传送门=￣ω￣=

2. 题解

好吧我承认我把这题写复杂了 QvQ

KB 又把这题秒杀了 Orz

但还是很有意思的 QvQ

蒟蒻我写的是扩展埃氏筛

复杂度约为 $O(L^{0.7}+R^{0.7})$

并且不需要 $R-L≤1000000$这个条件

（也就是说题目把 $R$开到 $10^{10}$并且 $L$任取一个小于 $R$的数都是可以过的，只要把数组开大就行了）

空间复杂度是 $O(\sqrt R)$的

具体看代码注释吧 QvQ

/*
 * 素数密度.cpp
 * This file is part of 素数密度
 *
 * Copyright (C) 2018 - xzy
 *
 * 素数密度 is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * 素数密度 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with 素数密度. If not, see <http://www.gnu.org/licenses/>.
 */


#include <bits/stdc++.h>

#define SQS (50000)//sqrt(R) 的范围

using namespace std;

int pre[SQS], suf[SQS];

//设 sum[i] 表示区间 [1,i] 的素数个数，那么：
//pre[i]=sum[i],suf[i]=sum[x/i],x 是下面这个函数的参数 x
//这样设状态是为了节省空间，能让空间变为根号 x 的级别

int E_Sieve(int x)//返回值为 sum[x]
{
    if (x <= 1) return 0;//特判
    int sqx = sqrt(x);//计算 sqrt(x)（根号 x)
    for (int i = 1; i <= sqx; i += 1)//初始假设所有的数都是素数
        pre[i] = i - 1, suf[i] = x / i - 1;
    //下面开始筛去合数
    for (int p = 2; p <= sqx; p += 1)//枚举 [2,sqrt(x)] 内素数
    {
        if (pre[p] == pre[p - 1]) continue;//如果 p 不是质数就 continue
        //扩展埃氏筛的转移式：f[i]-=f[i/p]-f[p-1]
        //这个转移式我就不在这说明了，属于算法内容，自行 google 吧（百度很难搜到的样子）
        int t = pre[p - 1];
        for (int i = 1; i <= sqx / p; i += 1)
            suf[i] -= suf[i * p] - t;
        for (int i = sqx / p + 1; i <= min(sqx, x / p / p); i += 1)
            suf[i] -= pre[x / i / p] - t;
        //上面这两个 for 都是筛去 suf[1,sqx] 中的合数的
        for (int i = sqx; i >= p * p; i -= 1)
            pre[i] -= pre[i / p] - t;
        //这个 for 是筛去 pre[1,sqx] 中的合数
    }
    return suf[1];//suf[1]=sum[x]
}

int L, R;

int main(int argc, char const* argv[])
{
    scanf("%d%d", &L, &R), printf("%d\n", E_Sieve(R) - E_Sieve(L - 1));//因为返回的是前缀和嘛，相减就是了
    return 0;
}

话说加上注释代码真丑，再发一遍没有注释的（我真无聊）：

/*
 * 素数密度.cpp
 * This file is part of 素数密度
 *
 * Copyright (C) 2018 - xzy
 *
 * 素数密度 is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * 素数密度 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with 素数密度. If not, see <http://www.gnu.org/licenses/>.
 */


#include <bits/stdc++.h>

#define SQS (50000)

using namespace std;

int pre[SQS], suf[SQS];

int E_Sieve(int x)
{
    if (x <= 1) return 0;
    int sqx = sqrt(x);
    for (int i = 1; i <= sqx; i += 1)
        pre[i] = i - 1, suf[i] = x / i - 1;
    for (int p = 2; p <= sqx; p += 1)
    {
        if (pre[p] == pre[p - 1]) continue;
        int t = pre[p - 1];
        for (int i = 1; i <= sqx / p; i += 1)
            suf[i] -= suf[i * p] - t;
        for (int i = sqx / p + 1; i <= min(sqx, x / p / p); i += 1)
            suf[i] -= pre[x / i / p] - t;
        for (int i = sqx; i >= p * p; i -= 1)
            pre[i] -= pre[i / p] - t;
    }
    return suf[1];
}

int L, R;

int main(int argc, char const* argv[])
{
    scanf("%d%d", &L, &R), printf("%d\n", E_Sieve(R) - E_Sieve(L - 1));
    return 0;
}