问题陈述
当一个正整数的质因数为质数时,该正整数被称为“质因数质数”。例如,$12$ 是质因数,因为 $12 = 2 \times 2 \times 3$ 的质因数个数是 $3$,它是质数。另一方面,$210$ 不是质因数,因为 $210 = 2 \times 3 \times 5 \times 7$ 的质因数个数是 $4$,这是一个合数。
在此问题中,给定一个整数区间 $[l, r]$。你的任务是编写一个程序来计算区间内素数素数的数量,即 $l$ 和 $r$ 之间(包括 $l$ 和 $r$)之间的素数素数的数量。
输入
输入由单个测试用例组成,格式如下。
$l$ $r$
一行包含两个整数$l$和$r$($1 \le l \le r \le 10^9$),表示一个整数区间$[l, r]$。您可以假设 $0 \le r - l < 1{,}000{,}000$。
输出
打印 $[l, r]$ 中质因数的个数。
示例输入 1
1 9
样本输入 1 的输出
4
示例输入 2
10 20
样本输入 2 的输出
6
示例输入 3
575 57577
样本输入 3 的输出
36172
示例输入 4
180 180
样本输入 4 的输出
1
示例输入 5
9900001 10000000
样本输入 5 的输出
60997
示例输入 6
999000001 1000000000
样本输入 6 的输出
592955
注意
在第一个示例中,$[l, r]$ 中有 4 个素数素数:$4$、$6$、$8$ 和 $9$。