试题描述

形如4n+1的数被称为“H数”，乘法在“H数”组成的集合内是封闭的。在这个集合中只能被1和本身整除的数叫做“H-素数”（不包括1），其余的数被称为“H-合数”。一个“H-合成数”是一个能且只能分解成两个“H-素数”乘积的“H-合数”（可能有多种分解方案）。比如441=21*21=9*49，所以441是“H-合成数”。125=5*5*5，所以125不是“H-合成数”。

求0到h范围内“H-合成数”的个数。

输入

输入包含若干行，每行一个小于等于1000001的整数h，输入0时表示结束。

输出

对于每一行输入，输出一个数，表示答案。

输入示例

21

85

0

输出示例

0

5

一道很棒的数学题。

思路：先筛出“素数”，然后将“素数”两两相乘，枚举出范围以内的“合成数”，再计算前缀和。最后直接输出。

#include
     
      #include
      
       #include
       
        #define INF 1000001using namespace std;bool ip[250001],hp[250001];//ip记录“素数”，hp记录“合成数” int s[250001];//前缀和int main(){	int R=sqrt(INF);	for(int i=5;i<=R;i+=4){//“素数”筛法		if(!ip[i/4]){			for(int j=5;i*j<=INF;j+=4) ip[i*j/4]=1;		}	}	for(int i=5;i<=R;i+=4){//两两相乘，枚举“合成数” 		for(int j=i;i*j<=INF;j+=4){			if(!ip[i/4]&&!ip[j/4]) hp[i*j/4]=1;		}	}	for(int i=1;i<=INF/4;i++){//计算前缀和（前i个H数中的“合成数”个数） 		s[i]=s[i-1];		if(hp[i]) s[i]++;	}	while(1){		int h;		cin>>h;		if(h==0) return 0;		cout<