[AdditionalFile6027.zip](file://AdditionalFile6027.zip?type=additional_file)

#6027. 「from CommonAnts」质数计数 I

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

求满足$1< p \leq n$ 且 $p$ 的二进制表示最后两位为 $01$ 的质数 $p$ 有多少个。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数 $\pi$ 表示答案。

样例 1

输入

20

输出

3

质数 $5,13,17$ 满足要求。

样例 2

输入

100000

输出

4783

数据范围与提示

对于 $30\%$ 的数据，$1\leq n\leq 10^4$

对于 $50\%$ 的数据，$1\leq n\leq 10^7$

对于 $80\%$ 的数据，$1\leq n\leq 10^{10}$

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^{10}$