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

    ID: 5106 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-素数计数Min_25 筛整除分块埃氏筛洲阁筛

「from CommonAnts」质数计数 I

题目描述

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

输入格式

一行一个整数 nn。

输出格式

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

20
3
100000
4783

数据范围与提示

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

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

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

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