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

内存限制：512 MB 时间限制：2.000 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

求满足1<p≤n1< p \leq n1<p≤n 且 ppp 的二进制表示最后两位为 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^41≤n≤10​4​​

对于 50%50\%50% 的数据，1≤n≤1071\leq n\leq 10^71≤n≤10​7​​

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

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