【POJ 3292】 Semi-prime H-numbers

【POJ 3292】 Semi-prime H-numbers

打个表

题意是1 5 9 13...这样的4的n次方+1定义为H-numbers

H-numbers中仅仅由1*自己这一种方式组成 即没有其它因子的 叫做H-prime

两个H-prime的乘积叫做H-semi-prime 另一个要求是H-semi-prime仅仅能由两个H-prime组成 即4个H-number 不可由3个或几个H-number构成

筛出来个满足题意的表 把每一个数内满足的个数存起来O(1)输出就可以

代码例如以下:

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int sz = 1000001;

int IsPrim[sz+1];

int p[sz];

int tp;

void Init()

{

    memset(IsPrim,0,sizeof(IsPrim));//H-numbers都初始化0 即默认都为H-prime

    int i,j,cnt;

    tp = 1;

    for(i = 5; i <= sz; i += 4)

    {

        for(j = 5; j*i <= sz; j += 4)

        {

            if(IsPrim[i] || IsPrim[j])//两个数有一个不是H-prime 组合就不为H-semi-prime

                IsPrim[i*j] = -1;

            else IsPrim[i*j] = 1;//否则组合为H-semi-prime 注意 H-semi-prime就不为H-prime了 因为顺序枚举 后面遍历到的之前肯定会推断一下 故不会漏判

        }

    }

    cnt = 0;

    for(i = 1; i <= 1000001; ++i)

    {

        if(IsPrim[i] == 1) cnt++;

        p[tp++] = cnt;

    }

}

int main()

{

    Init();

    int h;

    while(~scanf("%d",&h) && h)

    {

        h = (h-1)/4*4+1;

        printf("%d %d\n",h,p[h]);

    }

    return 0;

}