UVA11105

在这里插入图片描述

线性筛即可。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const int MAXN = 1000001;

bool IsNotHPrimer[MAXN + 1];

bool IsSemiHPrimer[MAXN + 1];

int sum[MAXN + 1];

vector<int> HPrimer;

void InitIsHPrimer() {

	for (int i = 5; i <= MAXN; i += 4) {
		if (IsNotHPrimer[i]) {
			continue;
		}
		HPrimer.push_back(i);
		for (int j = 1; i * j <= MAXN; j += 4) {
			IsNotHPrimer[i * j] = true;
		}
	}

	for (int i = 0; i < HPrimer.size(); ++i) {
		for (int j = 0; j < HPrimer.size(); ++j) {
			const int& P1 = HPrimer[i];
			const int& P2 = HPrimer[j];
			if (P1 * P2 > MAXN) {
				break;
			}
			IsSemiHPrimer[P1 * P2] = true;
		}
	}

	for (int i = 2; i <= MAXN; ++i) {
		sum[i] = sum[i - 1] + IsSemiHPrimer[i];
	}

}

int main(){

	int n;
	InitIsHPrimer();
	while (cin >> n && n) {
		printf("%d %d\n", n, sum[n]);
	}

	return 0;

}