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

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

题目描述

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

输入格式

一行一个整数 nn

输出格式

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

样例

样例输入 1

20

样例输出 1

3

样例解释 1

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

样例输入 2

100000

样例输出 2

4783

数据范围与提示

对于 30%30\% 的数据,1n1041\leq n\leq 10^4

对于 50%50\% 的数据,1n1071\leq n\leq 10^7

对于 80%80\% 的数据,1n10101\leq n\leq 10^{10}

对于 100%100\% 的数据,1n3×10101\leq n\leq 3\times 10^{10}