Poj 3292: Semi-prime H-numbers

poj3292.md

Poj 3292: Semi-prime H-numbers

題目

分析

擴展 sieve of Eratosthenes + 建前綴表

實作時注意，int 很容易溢位……建議用 long long

AC Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1000001 + 1;
vector<ll> h_primes;
bool is_h_prime[N];
bool is_semi_h_prime[N];
int s[N];


void init() {
    fill(is_h_prime, is_h_prime + N, true);
    fill(is_semi_h_prime, is_semi_h_prime + N, false);

    for (ll i = 5; i < N; i += 4) {
        if (is_h_prime[i]) {
            h_primes.push_back(i);
            for (ll j = i * i; j < N; j += i * 4)
                is_h_prime[j] = false;
        }
    }

    for (size_t i = 0; i < h_primes.size(); i++) {
        for (size_t j = i; j < h_primes.size(); j++) {
            ll product = h_primes[i] * h_primes[j];
            if (product >= N)
                break;
            is_semi_h_prime[product] = true;
        }
    }

    s[0] = 0;
    for (int i = 1; i < N; i++) {
        if (is_semi_h_prime[i])
            s[i] = s[i-1] + 1;
        else
            s[i] = s[i-1];
    }
}

int main() {
    init();

    int h;
    while (scanf("%d", &h)) {
        if (h == 0) break;
        printf("%d %d\n", h, s[h]);
    }

    return 0;
}