文章目录
  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Source
  7. 7. Codes

Description

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.

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.

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

Codes

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1000010;
bool nhp[maxn+10];
bool ihsp[maxn+10];
int hp[maxn+10];
int ps[maxn+10];
int h, cnt=0;
int main()
{
for(int i=5; i<maxn; i+=4)
{
if(nhp[i]) continue;
hp[cnt++]=i;
for(int j=i*5; j<maxn; j+=i*4)
nhp[j]=true;
}
for(int i=0; i<cnt; i++)
for(int j=0; j<=i && hp[i]*hp[j]<maxn; j++)
ihsp[hp[i]*hp[j]]=true;
for(int i=1; i<maxn; i++)
ps[i]=ps[i-1]+ihsp[i];
while(scanf("%d", &h)==1 && h)
printf("%d %d\n", h, ps[h]);
return 0;
}
文章目录
  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Source
  7. 7. Codes