You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

素数密匙

在一个遥远的古代王国，皇家密码师们发现了一个奇妙的加密方法。他们注意到，素数具有独特的性质，可以用来制作无法破解的密码。

为了确保信息安全，密码师们需要在特定范围内找出所有的素数来作为加密的密钥。这个范围通常由两个数字L和R来界定，分别代表密钥的最小值和最大值。

传说中最著名的密码师莱昂纳多发现，如果能准确计算出某个区间内素数的数量，就能预测密码的强度。这个数字被称为"素数密度"，它决定了密码被破解的难度。

现在，作为皇家密码学院的学徒，你的任务是开发一个快速的方法，来计算任意区间[L,R]内的素数个数。这个工具将帮助密码师们更好地设计加密系统，保护王国的机密信息。

UPD:

• 2024.8.12：加入一组 Hack 数据。

题目描述

给定 $L,R$，请计算区间 $[L,R]$ 中素数的个数。

$1\leq L\leq R < 2^{31}$，$R-L\leq 10^6$。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

2 11

样例输出 #1

5

提示

在样例中，区间[2,11]内的素数有：2,3,5,7,11，共5个。

请注意：

• 区间范围不能太大（R-L≤10^6），以确保计算速度
• 数值范围在计算机可处理范围内（小于2^31）
• 计算结果必须准确无误，因为任何错误都可能导致密码系统的崩溃