[POJ 3292] Semiprime Hnumbers
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 Hnumber is a positive number which is one more than a multiple of four: 1, 5, 9, 13, 17, 21,… are the Hnumbers. For this problem we pretend that these are the only numbers. The Hnumbers are closed under multiplication.
As with regular integers, we partition the Hnumbers into units, Hprimes, and Hcomposites. 1 is the only unit. An Hnumber h is Hprime if it is not the unit, and is the product of two Hnumbers in only one way: 1 × h. The rest of the numbers are Hcomposite.
For examples, the first few Hcomposites are: 5 × 5 = 25, 5 × 9 = 45, 5 × 13 = 65, 9 × 9 = 81, 5 × 17 = 85.
Your task is to count the number of Hsemiprimes. An Hsemiprime is an Hnumber which is the product of exactly two Hprimes. The two Hprimes may be equal or different. In the example above, all five numbers are Hsemiprimes. 125 = 5 × 5 × 5 is not an Hsemiprime, because it’s the product of three Hprimes.
Input
Each line of input contains an Hnumber ≤ 1,000,001. The last line of input contains 0 and this line should not be processed.
Output
For each inputted Hnumber h, print a line stating h and the number of Hsemiprimes 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

