← 返回题目列表

Codeforces · 113/C

C. 双喜临门

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

在数学课上,老师要求每个学生想出自己的幸运数字。作为数论爱好者,彼得选择了素数。鲍勃更有创意。他说数字t就是他的幸运数字,如果可以表示为:

t = a2 + b2,

现在,男孩们决定找出间隔 [l, r] (l ≤ r) 中的多少天适合结对编程。他们认为,当且仅当数字 i 同时对 Peter 来说是幸运的并且对 Bob 来说是幸运的时,i (l ≤ i ≤ r) 适合结对编程。帮助孩子们找出这样的天数。

输入

输入的第一行包含整数 l, r (1 ≤ l, r ≤ 3·108)。

输出

在唯一的一行中打印段 [l, r] 上的天数,这同时对 Peter 和 Bob 来说是幸运的。

示例

输入 #1

3 5

输出 #1

1

输入 #2

6 66

输出 #2

7