根基排序

自然数n的根基$\mathrm{rad}(n)$，即该数的所有质因数之积，如 $$\mathrm{rad}(504)=\mathrm{rad}(2^3\times 3^2\times 7)=2\times 3\times 7=42.$$ 规定$\mathrm{rad}(1)=1$，并计算不超过10的自然数的根基，可得 $$\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \mathrm{rad}(n) & 1 & 2 & 3 & 2 & 5 & 6 & 7 & 2 & 3 & 10 \end{matrix}$$ 将其按$\mathrm{rad}$从小到大排序，$\mathrm{rad}$相同的数再按其本身的大小排序，可得 $$\begin{matrix}n & 1 & 2 & 4 & 8 & 3 & 9 & 5 & 6 & 7 & 10 \\ \mathrm{rad}(n) & 1 & 2 & 2 & 2 & 3 & 3 & 5 & 6 & 7 & 10 \end{matrix}$$ 令$E(k)$为前n个自然数按上述方式排序后的第k个数，例如，$E(4)=8$、$E(6)=9$。

将前十万个自然数按上述方式排序，求$E(10000)$。

本题难度:

解答

用筛法计算根基后排序即得结果为$21417$。

注：以下为Python3代码，因math.prod是Python3中的新函数。

import math

target=100001
d=[[1] for i in range(target)]
n=2
while n < target:
    for i in range(n,target,n):
        d[i].append(n)
    n+=1
    while n < target and len(d[n])>1:
        n+=1

print(sorted([[math.prod(d[n]),n] for n in range(1,target)])[9999][1])