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

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

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

输入格式

一行一个整数 n

输出格式

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

样例

样例输入 1

20

样例输出 1

3

样例解释 1

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

样例输入 2

100000

样例输出 2

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}