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

Memory Limit:512 MB Time Limit:2.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

求满足1<p≤n1< p \leq n1<pnppp 的二进制表示最后两位为 010101 的质数 ppp 有多少个。

输入格式

一行一个整数 nnn

输出格式

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

样例

样例输入 1

20

样例输出 1

3

样例解释 1

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

样例输入 2

100000

样例输出 2

4783

数据范围与提示

对于 30%30\%30% 的数据,1≤n≤1041\leq n\leq 10^41n104

对于 50%50\%50% 的数据,1≤n≤1071\leq n\leq 10^71n107

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

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