poj3292 (H数)筛法

2017年04月25日 10点热度 0人点赞 0条评论
/*
问题描述
	形如4n+1的数被称为“H数”,乘法在“H数”组成的集合内是封闭的。在这个集合中只能被1和本身
整除的数叫做“H-素数”(不包括1,H-素数并不是真正的素数,而是在H数集合中是素数),其余的数被称为“H-合数”。一个“H-合成数”是一个能且只能
分解成两个“H-素数”乘积的“H-合数”(可能有多种分解方案)。比如441=21*21=9*49,所以441是
“H-合成数”。125=5*5*5,所以125不是“H-合成数”。
	求0~h范围内“H-合成数”的个数。
	输入格式
	输入若干行,每行一个小于等于1000001的整数h,一个0表示结束。
	输出格式
	对于每一行输入,输出一个数,表示答案。 
Sample Input
21 
85
789
0
Sample Output
21 0
85 5
789 62
*/
#include
#include
using namespace std;
int n;
bool is_prime[1000100];//大约1M空间,是否为h素数 
bool is_con[1000100];
int main(){
	//一次预处理 
	for(int i=5;i<1000002/5;i+=4)
	if(!is_prime[i])
	for(int j=5;i*j<1000002;j+=4)
		is_prime[i*j]=true;
	for(int i=5;i*i<1000002;i+=4)
	if(!is_prime[i])
	for(int j=i;i*j<1000002;j+=4)
	if(!is_prime[j])
		is_con[i*j]=true;
	while(scanf("%d",&n)&&n){
		int ans=0;
		for(int i=5;i<=n;i+=4)
		if(is_con[i]) ans++;
		printf("%d %dn",n,ans);
	}
	return 0;
}

未经允许不得转载!poj3292 (H数)筛法

update

纸上得来终觉浅, 绝知此事须躬行。