一个数恰有三个因子当且仅当它是某个素数的平方： $n = p^2$ 。
- 若 $n=p^2$ ，其因子为 $1,p,p^2$ 共 $3$ 个。
- 若有恰好 $3$ 个因子，则其素因子分解必须是 $p^2$ 的形式。
因此，区间 $[l,r]$ 内伪质数的个数等于满足 $p^2 \in [l,r]$ 的素数 $p$ 的个数。
令 $A=\lfloor \sqrt{r} \rfloor$ ， $B=\lfloor \sqrt{l-1} \rfloor$ ，答案为

P3508.第3题-伪质数

1000ms

Difficulty: 5

所属公司 : 阿里

算法与标签>数学

题目内容

众所周知，质数是指大于 $1$ 且只有 $1$ 及其本身两个因子的数。

Tk 学习质数后对这种特殊数产生极大的兴趣；

Tk 定义 伪质数 为一个大于 $1$ 并且恰有三个不同正因子的整数；

现在，给定一个闭区间 $[l,r]$ ，Tk 想知道区间中伪质数的个数。

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数；

此后每组测试数据描述如下：

在一行上输入两个整数 $l,r(1≤l≤r≤ 10^{14})$ ，表示询问区间的左右端点。

对于每一组测试数据，新起一行。

输出一个整数，表示区间内伪质数的个数。

输入

2
1 10
13 15

输出

2
0

输入

预期输出（选填）