- POJ 3292 - Semi-prime H-numbers
- Time: 1000MS
- Memory: 65536K
- 难度: 初级
- 分类: 同余模
问题描述
一个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数。
解题思路
感觉跟同余模扯不上关系。
筛法打表，再直接输出。
水题。
AC 源码
//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;
}
