打一下表，预处理一下，没有什么难度了。

#include "iostream"


using namespace std;

#define MAXN 1000005

int h[MAXN];

void hnumbers()
{
    memset(h, 0, sizeof(h));
    for (int i = 5; i <= 1000001; i += 4) {
        for (int j = 5; j <= 1000001; j += 4) {
            if (i * j > 1000001)
            {
                break;
            }
            else
            {
                if (h[i] == 0 && h[j] == 0) {
                    h[i*j] = 1;//h-semi
                }
                else h[i*j] = -1;//h-combo
            }
        }
    }
    int countt = 0;
    for (int i = 0; i <= 1000001; i++) {
        if (h[i] == 1) {
            countt++;
        }
        h[i] = countt;
    }
}

int main()
{
    hnumbers();
    int n;
    while (cin>>n && n)
    {
        cout << n << ‘ ‘ << h[n] << endl;
    }
}

poj3292