n의 근인 rad(n)은 서로 다른 소수 n의 곱이다. 예를 들어, 504=23*32*7이고, rad(504)=2*3*7=42이다.
n이 1이상, 10이하일 때 rad(n)을 계산하고, rad(n)을 기준으로 정렬하고, 근 값이 같을 때 n 값에 따라 정렬하면 위의 표와 같다:
E(k)를 정렬된 n의 k번째 요소라고 하자. 예를 들어, E(4)=8이고, E(6)=9이다.
rad(n)이 1이상, 10만 이하의 값으로 정렬되었을 때, E(10000)을 구하시오.
--------------------------------------------------------------------------
미리 만들어 둔 약수 함수를 이용해서 결과 중 소수만 찾으면 rad(n) 값을 구할 수 있다.
10만개 결과 리스트에 대해 rad(n)값을 1순위, n값을 2순위로 해서 정렬하면 답을 구할 수 있다. 파이썬 리스트의 인덱스가 0부터 시작하는 것 때문에 1만번째 값을 다른 것을 구하는 덕분에 다시 한 번 더 실행해야 되어서 시간이 좀 걸렸다.
약수 함수를 아무리 개선해도 성능에 한계가 있어서 문제에서 10만개를 요구했으니 다행이지 다른 문제처럼 몇조 단위의 처리를 요구했으면 시간내에 해결하지 못했을 것 같다.