# 2. 题解

KB 又把这题秒杀了 Orz

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

/*
* 素数密度.cpp
* This file is part of 素数密度
*
* Copyright (C) 2018 - xzy
*
* 素数密度 is free software; you can redistribute it and/or modify
* 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]
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
* 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;
}