← 返回题目列表

AtCoder · jag2017autumn_c

C. 素因子素数

中文机器翻译题面 查看原题

问题陈述

当一个正整数的质因数为质数时,该正整数被称为“质因数质数”。例如,$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$。