6

POJ 3292 - Semi-prime H-numbers

 2 years ago
source link: https://exp-blog.com/algorithm/poj/poj3292-semi-prime-h-numbers/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Semi-prime H-numbers

一个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;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK