POJ-3292 Semi-prime H-numbers---筛素数

题目链接：

https://vjudge.net/problem/POJ-3292

题目大意：

定义一种数叫H-numbers，它是所有能除以四余一的数。

在H-numbers中分三种数：

1、H-primes，这种数只能被1和它本身整除，不能被其他的H-number整除，例如9是一个H-number，能被1，3，9整除，但3不是H-number，所以他是H-primes。

2、H-semi-primes是由两个H-primes相乘得出的。

3、剩下的是H-composite。

问给一个数，求1到这个数之间有多少个H-semi-primes。

思路：

先打表出所有的H-prime，然后打表出H-semi-prime，求前缀和

 #include<iostream>

 #include<vector>

 #include<queue>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<set>

 #include<map>

 #include<cmath>

 using namespace std;

 typedef pair<int, int> Pair;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 int T, n, m;

 const int maxn = +;

 bool is_Hprime[maxn];

 ll sum[maxn], tot, c;

 ll ans[maxn];

 void init()

 {

     for(int i = ; i < maxn; i += )is_Hprime[i] = ;

     for(int i = ; i < maxn; i += )//筛选出所有的H-prime

     {

         if(is_Hprime[i])

         {

             sum[tot++] = i;

             for(int j =  * i; j < maxn; j += i)is_Hprime[j] = ;

         }

     }

     for(int i = ; i < tot; i++)//构造H-semi-primes

     {

         for(int j = i; j < tot; j++)

         {

             ll t = sum[i] * sum[j];

             if(t > )break;

             if(t %  == )ans[t] = ;

         }

     }

     for(int i = ; i < maxn; i++)ans[i] += ans[i - ];

 }

 int main()

 {

     init();

     while(scanf("%d", &n) && n)

         printf("%d %lld\n", n, ans[n]);

 }