题目描述

小明想知道一个区间里有多少个“质数”。

什么是质数？
质数就是一个大于 1 的自然数，除了 1 和它自己，不能被别的数整除。
比如：$2, 3, 5, 7, 11, 13 \dots$ 都是质数。
$1$ 不是质数。

现在给你两个正整数 $L$ 和 $R$，请你数一数从 $L$ 到 $R$ 之间（包括 $L$ 和 $R$）一共有多少个质数。

注意：

• $L$ 和 $R$ 可能很大，最大到 $2^{31} - 1$ 左右（大约 21 亿）。
• 但是 $R - L \le 10^6$（也就是区间长度不超过 100 万）。
• 请你编一个又快又聪明的程序来数。

输入格式

第一行，两个正整数 $L$ 和 $R$。

输出格式

一行，一个整数，表示区间中素数的个数。

2 11

5

100000000 100000100

6