POJ 3292 Semi-prime H-numbers：H-數半素數計數解法

H-數體系與核心定義

POJ 3292 引入 Hilbert 提出的 H-數體系：形如 4k+1 (k≥0) 的正整數（1, 5, 9, 13, 17, ...）。在這個封閉乘法體系中：

• 單位元：只有 1
• H-素數：非單位元，且唯一分解為 1 × 自身（在 H-數意義下）
• H-合數：其餘 H-數
• H-半素數：恰好是兩個 H-素數乘積的 H-數（允許相同）

任務：對每個輸入 h ≤ 1,000,001，輸出 [1, h] 區間內 H-半素數的個數。

篩法預處理三步驟

1. 篩選 H-素數（類埃氏篩）

僅考慮 H-數作為潛在因子。對 i = 5; i*i ≤ MAXN; i += 4，若 vis[i] == 0 則為 H-素數，標記其倍數 j = i*i; j ≤ MAXN; j += 4*i 為合數（步長 4*i 保證乘積仍為 H-數）。

2. 生成 H-半素數標記表

收集所有 H-素數至陣列 hp[]。雙重迴圈枚舉 hp[i] * hp[j] ≤ MAXN (j ≥ i)，將乘積位置 vis[product]++。計數器 vis[x] ≥ 1 即表示 x 為 H-半素數（含平方情況）。

3. 前綴和陣列答查詢

建立 ans[i] 為 [1, i] 內 H-半素數累計數。查詢時直接輸出 ans[h]，O(1) 回答。

核心代碼實現

#include <cstdio>
#include <cstring>
#include <cmath>
const int MAXN = 1000001;
int vis[MAXN], hp[MAXN], ans[MAXN];

int main() {
    int hp_cnt = 0, limit = sqrt(MAXN);
    // 篩 H-素數
    for (int i = 5; i <= limit; i += 4)
        if (!vis[i])
            for (int j = i*i; j < MAXN; j += 4*i)
                vis[j] = 1;
    for (int i = 5; i < MAXN; i += 4)
        if (!vis[i]) hp[++hp_cnt] = i;

    memset(vis, 0, sizeof(vis));
    // 標記 H-半素數
    for (int i = 1; i <= hp_cnt && hp[i]*hp[i] < MAXN; ++i)
        for (int j = i; j <= hp_cnt && hp[i]*hp[j] < MAXN; ++j)
            ++vis[hp[i] * hp[j]];

    // 前綴和
    for (int i = 1; i < MAXN; ++i)
        ans[i] = ans[i-1] + (vis[i] >= 1);

    int h;
    while (scanf("%d", &h) && h)
        printf("%d %d\n", h, ans[h]);
    return 0;
}

複雜度與關鍵點總結

• 時間：篩法 O(N log log N)，雙重迴圈約 O(π_H(N)^2)，實測 < 0.1s
• 空間：三個 1e6 級陣列，約 12 MB
• 關鍵細節：步長 4*i、j ≥ i 避免重複、vis[x]++ 而非布林標記以區分多重分解