UVA11105

线性筛即可。

#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;}