类似于筛选素数的方法，枚举前缀和即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <cstdio>
using namespace std;
const int maxn = 1000010;
bool nhp[maxn];
int hp[maxn],hpnum;
int cnt[maxn];
void pre() {
for(int i = 5; i < 1010; i += 4)
if(!nhp[i])
for(int j = i * i; j < maxn; j += i)
nhp[j] = true;
for(int i = 5; i < maxn; i+=4)
if(!nhp[i]) hp[hpnum++] = i;
for(int i = 0; i < hpnum; ++i)
for(int j = 0; j < hpnum && hp[i] * hp[j] < maxn; ++j)
cnt[hp[i]*hp[j]] = 1;
for(int i = 1; i < maxn; ++i) cnt[i] += cnt[i - 1];
}
int main() {
pre();
int n;
while(~scanf("%d", &n) && n)
printf("%d %d\n", n, cnt[n]);
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **