POJ 3292 - Semi-prime H-numbers

http://poj.org/problem?id=3292

概要

4n+1 の形で表わされる正の整数を H-numbers と呼ぶ．H-numbers は乗算に関して閉じている．

H-number h が単位元ではなく，そして2つの H-number の積で表わしたとき 1 * h の1通りしかないとき，h は H-prime であると呼ぶ．

2つの H-prime の積で表わされる H-number を H-semi-prime とするとき，与えられた H-number h 以下の H-semi-prime がいくつあるか答える．

制約

• h <= 1000001

解法

あらかじめ，エラトステネスの篩の要領で H-prime をすべて生成し，H-semi-prime をすべて生成して数を数えておく．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   static const int M = 1000001;
 8   static bool sieve[M+1];
 9   vector<int> primes;
10   for (int i = 5; i <= M; i += 4) {
11     if (!sieve[i]) {
12       primes.push_back(i);
13       for (int j = 5; i*j <= M; j += 4) {
14         sieve[i*j] = true;
15       }
16     }
17   }
18   static int cnt[M+1];
19   for (vector<int>::const_iterator it = primes.begin(); it != primes.end(); ++it) {
20     for (vector<int>::const_iterator jt = it; jt != primes.end() && *jt <= M / *it; ++jt) {
21       cnt[*it * *jt] = 1;
22     }
23   }
24   for (int i = 1; i <= M; i++) {
25     cnt[i] += cnt[i-1];
26   }
27 
28   int H;
29   while (scanf("%d", &H) != EOF && H != 0) {
30     printf("%d %d\n", H, cnt[H]);
31   }
32   return 0;
33 }