质数计数 I

题目描述:

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

输入格式:

一行一个整数 n。

输出格式:

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

样例输入:

样例1：
20

样例2：
100000

样例输出:

样例1：
3

样例2：
4783

提示:

样例解释 1

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

 

对于 30% 的数据，1≤n≤10⁴

对于 50% 的数据，1≤n≤10⁷

对于 80% 的数据，1≤n≤10¹⁰

对于 100% 的数据，1≤n≤3×10¹⁰

时间限制: 1000ms
空间限制: 256MB

---