题意：参考https://blog.csdn.net/lyy289065406/article/details/6648537
一个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数。
思路 ：直接暴力打表 因为h <=1e6 而 打表的复杂度是 log4(h)*log4(h)所以 不会超时 不要误以为是n^2的复杂度
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<iostream>
using namespace std;
const int maxn=1e6+;
int H_primes[maxn+];
int vis[maxn+];
int ans[maxn];
int cnt;
void init(){
cnt=;
for(int i=;i<=maxn;i+=){
for(int j=;j<=maxn;j+=){
int mul=i*j;
if(mul>maxn)break;
if(H_primes[i]==&&H_primes[j]==)
H_primes[mul]=;
else H_primes[mul]=-;
} }
for(int k=;k<=maxn;k++){
if(H_primes[k]==)
cnt++;
ans[k]=cnt;
}
}
int main(){
init();
int n;
while(scanf("%d",&n)==&&n){
printf("%d %d\n",n,ans[n]);
}
return ;
}