题意：题目比较容易混淆，要搞清楚一点，这里面所有的定义都是在4×k+1（k>=0）这个封闭的集合而言的，不要跟我们常用的自然数集混淆。
题目要求我们计算 H-semi-primes， H-semi-primes是 两个H-primes的乘积， H-primes的定义为：在这个集合中只能由1和它本来相乘得来，并且1不是 H-primes；
分析：这个题目我一开始是想打表记录一下的，但是没有筛法的效率，数据量过大，程序崩溃了（连超时的机会都不给我），看了多个别人的做法才知道，这个题目考查的是对于素数筛法，我们需要对素数筛法有一些变形。和正常筛法是不太一样的，这个有三种数，H-semi-primes，H-primes， H-composite，这三种数我们需要给他们标上不同的号，而且必须是不同的号，否则筛法会出错误，最后题目问的是（1，h）之间有多少个，我们应该使用一个数组记录这个答案，以便打表以后在o（1）的复杂度就找到答案。
注意：可能有人感觉会有漏解，其实不会，有人可能会担心这一点，类似这样，5×25怎么办？ 但是25的标记一定不是0，25在5×5的时候就被标记了1，我们在后面能遇到的能被两个数乘积表达的数，在以前的时候就肯定已经被表达出来，并且标记过了。
感悟：感觉素数筛法好神奇，它的变形好巧妙，好精美。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 1000001 int prime[maxn+10]; int ans[maxn+10]; void make(){ memset(prime,0,sizeof(prime)); ///H—prime 标记为 0 for(int i = 5;i <= maxn;i += 4){ for(int j = 5;j <= maxn;j += 4){ if(i*j > maxn) break; if(prime[i]==0 && prime[j]==0)///这个判断0的充要条件就是题目中给的要求，只能是两个H-prime ///任意一个为1或者2都不可以 prime[i*j] = 1;///H-semi-primes标记为1； else prime[i*j] = 2;/// H-composites必须为2或者其他 } } } void get_ans(){ int tot = 0; for(int i = 1;i <= maxn;i++){ if(prime[i] == 1) tot++;///don't forget prime[i] shoule only be 1; ans[i] = tot; } } int main(){ int h; make(); get_ans(); while(~scanf("%d",&h)){ if(!h) break; printf("%d %d ",h,ans[h]); } return 0; }