Semi-prime H-numbers
An H-number is a positive number which is one more than a multiple of four: 1, 5, 9, 13, 17, 21,... are the H-numbers. For this problem we pretend that these are the only numbers. The H-numbers are closed under multiplication.This problem is based on an exercise of David Hilbert, who pedagogically suggested that one study the theory of 4n+1 numbers. Here, we do only a bit of that.
As with regular integers, we partition the H-numbers into units, H-primes, and H-composites. 1 is the only unit. An H-number h is H-prime if it is not the unit, and is the product of two H-numbers in only one way: 1 × h. The rest of the numbers are H-composite.
For examples, the first few H-composites are: 5 × 5 = 25, 5 × 9 = 45, 5 × 13 = 65, 9 × 9 = 81, 5 × 17 = 85.
Your task is to count the number of H-semi-primes. An H-semi-prime is an H-number which is the product of exactly two H-primes. The two H-primes may be equal or different. In the example above, all five numbers are H-semi-primes. 125 = 5 × 5 × 5 is not an H-semi-prime, because it's the product of three H-primes.
Input
Each line of input contains an H-number ≤ 1,000,001. The last line of input contains 0 and this line should not be processed.
Output
For each inputted H-number h, print a line stating h and the number of H-semi-primes between 1 and h inclusive, separated by one space in the format shown in the sample.
Sample Input
21
85
789
0
Sample Output
21 0
85 5
789 62
Source
Waterloo Local Contest, 2006.9.30
题目类型：Euler筛法
算法分析：将每个H-素数定义好后，使用类似Euler筛法的思想预打表，维护前缀和并查询
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 66; int primelist[maxn], len, sum[maxn]; bool prime[maxn]; void PP() { memset (sum, 0, sizeof (sum)); memset (prime, true, sizeof (prime)); len = 0; prime[0] = prime[1] = false; for (int i = 5; i < maxn; i += 4) { if (prime[i]) primelist[len++] = i; for (int j = 0; j < len; j++) { if (i * primelist[j] > maxn) break; if (prime[i] && prime[primelist[j]]) sum[i*primelist[j]] = 1; prime[i*primelist[j]] = false; if (i % primelist[j] == 0) break; } } for (int i = 1; i < maxn; i++) sum[i] += sum[i-1]; } int main() { // CFF; PP (); int n; while (scanf ("%d", &n) != EOF) { if (n == 0) break; printf ("%d %d\n", n, sum[n]); } return 0; } |
- « 上一篇：poj3273
- poj3421：下一篇 »