poj3292 素数打表

正确版

/*
Time:2019.12.7
Author: Goven
type：素数打表
ref:https://blog.csdn.net/lyy289065406/article/details/6648537
*/
#include<iostream>
#include<cstring>
#define MAXH 1000005
using namespace std;

int H_prime[MAXH], res[MAXH];
int cnt;

void primeTable(){
    cnt = 0;
    H_prime[cnt++] = 5;
    for (int i = 5; i < MAXH; i += 4) {
        int flag = 1;
        for (int j = 0; H_prime[j] * H_prime[j] <= i; j++) {
            if (i % H_prime[j] == 0) {
                flag = 0; break;
            }
        }
        if (flag) H_prime[cnt++] = i;
    }   
}

void getH_semi_primes() {
    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j < cnt; j++) {
            if (MAXH / H_prime[i] < H_prime[j]) break;
            res[H_prime[i] * H_prime[j]] = 1;
        }
    }
    
    for (int i = 1; i < MAXH; i++) {
        res[i] += res[i - 1];
    }
}

int main()
{
    primeTable();
    getH_semi_primes();
    int h;
    while (cin >> h && h) {
        cout << h << " " << res[h] << endl;
    }
    return 0;
}

错误版-超时：

/*
Time:2019.12.7
Author: Goven
type：素数打表 
ref:
err:Time Limit Exceeded
*/
#include<iostream>
#include<cstring>
#define MAXH 1000005
using namespace std;

bool isH_prime[MAXH];
int H_prime[MAXH];
int cnt;

void primeTable(){
    memset(isH_prime, false, sizeof(isH_prime));
    int flag;
    cnt = 0;
    H_prime[cnt++] = 5;
    isH_prime[5] = true;
    for (int i = 5; i < MAXH; i += 4) {
        flag = 1;
        for (int j = 0; H_prime[j] * H_prime[j] <= i; j++) {
            if (i % H_prime[j] == 0) {
                flag = 0; break;
            }
        }
        if (flag) H_prime[cnt++] = i, isH_prime[i] = true;
    }   
}

int main()
{
    primeTable();
    int h;
    while (cin >> h && h) {
        int res = 0;
        for (int i = 5; i <= h; i += 4) {
            for (int j = 0; j < cnt; j++) {
                if (i % H_prime[j] == 0 && (i / H_prime[j] % 4 == 1) && isH_prime[i / H_prime[j]]) {
                    res++;
                    break;
                }
            }
        }
        cout << h << " " << res << endl;
    }
    return 0;
}