Whenever we think of sorting integers, we tend to think of sorting them in ascending or
descending order. However, we can play around a bit and define new sorting criteria.
One criterion could be sorting numbers in terms of their summation of digits. Therefore
in this sorting criterion, 13 would come before 9 as sum of the digits of 13 is 4 and
that of 9 is 9.
In this problem, we are concerned with sorting numbers in the range 1 to 2000000 with the
following sorting criteria. Numbers in this range must be sorted in terms of the number
of factors in their prime factorization. Incase of a tie, the smaller number will come
first. For example, 20 = 2*2*5, so it has 3 numbers in its prime factorization. Similarly
35 = 5*7 has 2 numbers in its prime factorization. Therefore, 35 will come before 20
according to this criterion.
Each case of input will consist of a positive integer n<=2000000. The last case is
followed by a 0.
Total number of test cases can be as large as 100000.
For each case of input, there will be one line of output. It will consist of the case
number followed by the nth number in the range 1 to 2000000 after the sorting rule has
been applied. Look at sample output for further clarification.
Case 1: 1
Case 2: 2
Case 3: 3
Case 4: 5
Shamim Hafiz @ Next generation contest ĘC 4 @ UVA