Problem 124
Ordered radicals
The radical of n, rad(n), is the product of the distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.
If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get:
| Unsorted | Sorted | ||||
|---|---|---|---|---|---|
| n | rad(n) | n | rad(n) | k | |
| 1 | 1 | 1 | 1 | 1 | |
| 2 | 2 | 2 | 2 | 2 | |
| 3 | 3 | 4 | 2 | 3 | |
| 4 | 2 | 8 | 2 | 4 | |
| 5 | 5 | 3 | 3 | 5 | |
| 6 | 6 | 9 | 3 | 6 | |
| 7 | 7 | 5 | 5 | 7 | |
| 8 | 2 | 6 | 6 | 8 | |
| 9 | 3 | 7 | 7 | 9 | |
| 10 | 10 | 10 | 10 | 10 |
Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.
If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).
基排序
数n的基rad(n)，是指n的不同质因数之积。例如，504 = 23 × 32 × 7，所以rad(504) = 2 × 3 × 7 = 42。
如果我们计算1 ≤ n ≤ 10的rad(n)，并先按照rad(n)再按照n从小到大排序，我们得到：
| 排序前 | 排序后 | ||||
|---|---|---|---|---|---|
| n | rad(n) | n | rad(n) | k | |
| 1 | 1 | 1 | 1 | 1 | |
| 2 | 2 | 2 | 2 | 2 | |
| 3 | 3 | 4 | 2 | 3 | |
| 4 | 2 | 8 | 2 | 4 | |
| 5 | 5 | 3 | 3 | 5 | |
| 6 | 6 | 9 | 3 | 6 | |
| 7 | 7 | 5 | 5 | 7 | |
| 8 | 2 | 6 | 6 | 8 | |
| 9 | 3 | 7 | 7 | 9 | |
| 10 | 10 | 10 | 10 | 10 |
记E(k)是前n个数排序后的第k个数，例如，E(4) = 8以及E(6) = 9。
对1 ≤ n ≤ 100000按照rad(n)排序后，求E(10000)。