POJ3292Semiprime Hnumbers

转载请注明出处：優YoU   http://user.qzone.qq.com/289065406/blog/1309336489

 

大致题意：

一个H-number是所有的模四余一的数。

如果一个H-number是H-primes 当且仅当它的因数只有1和它本身（除1外）。

一个H-number是H-semi-prime当且仅当它只由两个H-primes的乘积表示。

H-number剩下其他的数均为H-composite。

给你一个数h,问1到h有多少个H-semi-prime数。

 

解题思路：

感觉跟同余模扯不上关系。。。

筛法打表，再直接输出。。。水题。。。

//Memory Time 
//4172K  63MS 

#include<iostream>
using namespace std;

const int size=1000001;

int H_Number[size+1];

/*筛法打表*/
void Table(void)
{
    memset(H_Number,0,sizeof(H_Number));  //H_Number[i]=0 表示 i为H-prime

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

            if(H_Number[i]==0 && H_Number[j]==0)  //i与j均为H-prime
                H_Number[multiply]=1;  //multiply为H-semi-primes
            else
                H_Number[multiply]=-1; //multiply为H-composite
        }
    }

    int Pcount=0; //H-prime计数器
    for(int k=1;k<=size;k++)
    {
        if(H_Number[k]==1)
            Pcount++;
        H_Number[k]=Pcount;   //从1到k有Pcount个H-semi-primes
    }
    return;
}

int main(void)
{
    Table();
    int h;
    while(cin>>h && h)
        cout<<h<<' '<<H_Number[h]<<endl;

    return 0;
}