题目链接

Semi-prime H-numbers POJ - 3292

思路

$$ 类似线性筛素数 $$

时间复杂度

$$ O(N) $$

代码

#include <cstdio>
#include <vector>

using namespace std;


const int MAXN = 1000100;
int is_h_prime[MAXN];
int ans[MAXN];
int pi[MAXN];
vector<int> h_prime;

int main() {

    int n = 1000001;
    int cnt = 0;
    for (int i = 5; i <= n; i += 4) {
        pi[i] = i;
    }
    for (int i = 5; i <= n; i += 4) {
        if (pi[i] == i) {
            h_prime.push_back(i);
            is_h_prime[i] = 1;
            cnt++;
        }
        for (int j = 0; j < cnt && 1LL * h_prime[j] * i <= n; j++) {
            pi[h_prime[j] * i] = h_prime[j];
            if (i % h_prime[j] == 0) {
                break;
            }
        }
    }

    for (int i = 5; i <= n; i += 4) {
        if (pi[i] != i) {
            int w = i / pi[i];
            if (is_h_prime[w]) {
                ans[i] = 1;
            }
        }
    }
    for (int i = 5; i <= n; i++) {
        ans[i] += ans[i - 1];
    }
    int x;
    while (scanf("%d", &x), x) {
        printf("%d %d\n", x, ans[x]);
    }


    return 0;
}