POJ3292 UVA11105 Semi-prime H-numbers【筛法打表】

问题链接：POJ3292 UVA11105 Semi-prime H-numbers。

问题简述：参见上述链接。

问题分析：

H-number：4n+1的数，n>=0，例如1,5,9,13,17,21,......。

H-prime：H-number数并且其因子只有1和它本身。

H-semi-prime：两个H-prime的乘积。

H-composite：其他H-number数。

需要注意的一点是，两个H-number的乘积=(4n+1)*(4m+1)=4*4m*n+4n+4m+1是一个H-number数。

这个问题是对于输入的h，求1-h之间H-semi-prime数的数量。

根据筛选法的原理进行筛选，先筛选出H-semi-prime，再做一下统计计算。

程序说明：

数组h_number[]，若h_number[i]=0表示i为H-prime，h_number[i]=1表示i为H-semi-primes，h_number[i]=-1表示i为H-composite。

统计处理后，h_number[i]=k表示1-i中有k个H-semi-primes。

AC的C++语言程序如下：

/* POJ3292 UVA11105 Semi-prime H-numbers */

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_H_NUMBER = 1000001;
int h_number[MAX_H_NUMBER + 1];     //h_number[i]=0表示i为H-prime

void maketable(int n)
{
    memset(h_number, 0, sizeof(h_number));

    for(int i=5; i<=n; i+=4)
        for(int j=5; j<=n; j+=4) {
            int product = i * j;
            if(product > n)
                break;

            if(h_number[i] == 0 && h_number[j] == 0)
                h_number[product] = 1;      // product为H-semi-primes
            else
                h_number[product] = -1;     // product为H-composite
        }

    // 统计H-prime
    int hpcount = 0;
    for(int i=1; i<=n; i++) {
        if(h_number[i] == 1)
            hpcount++;
        h_number[i] = hpcount;  // 1-i有hpcount个H-prime
    }
}

int main()
{
    int h;

    maketable(MAX_H_NUMBER);

    while(cin >> h && h)
        cout << h << " " << h_number[h] << endl;

    return 0;
}