프로젝트 오일러 124번

The radical of \(n\), \({\rm rad}(n)\), is the product of the distinct prime factors of \(n\). For example, \(504 = 2^3 \times 3^2 \times 7\), so \({\rm rad}(504) = 2 \times 3 \times 7 =42\).

If we calculate \({\rm rad}(n)\) for \(1 \le n \le 10\), then sort them on \({\rm rad}(n)\), and sorting on \(n\) if the radical values are equal, we get:

Unsorted			Sorted
\(n\)	\({\rm rad}(n)\)		\(n\)	\({\rm 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 \(k\)th element in the sorted \(n\) column; for example, \(E(4)=8\) and \(E(6)=9\).

if \({\rm rad}(n)\) is sorted for \(1 \le n \le 100000\), find \(E(10000)\).

---

\({\rm rad}(n)\) 은 자연수 \(n\) 의 소인수들의 곱을 나타낸다. 예를 들어, \(504 = 2^3 \times 3^2 \times 7\) 로 소인수분해 되기 때문에 \({\rm rad}(504)=2 \times 3 \times 7 = 42\). 가 된다.

\(1 \le n \le 10\) 에 대해서 \({\rm rad}(n)\) 을 구하고, \({\rm rad}(n)\) 에 대해서 오름차순으로 정리한 후, \({\rm rad}(n)\) 값이 같은 것들에 대해서는 다시 \(n\) 에 대해서 오름차순으로 정리하면 위 표와 같은 결과를 얻는다.

\(E(k)\) 가 오름차순으로 정리된 상태에서 \(k\) 번째 해당하는 \(n\) 값을 나타낸다고 하자. 예를 들어, \(E(4) =8\) 이고 \(E(6) = 9\) 이다. \(1 \le n \le 100000\) 에 대해서 \({\rm rad}(n)\) 을 구하고, 위와 같은 방법으로 오름차순으로 정렬하였을 때 \(E(10000)\) 의 값을 구하시오. 

문제에서 예로 본 것처럼 \(n=10\) 까지만 생각해 보도록 하겠다.

먼저 \(10\) 이하의 소수들을 준비해야 한다. 

prime = [2, 3, 5, 7]

그리고 다음과 같은 리스트를 만든다.

result = [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 10]]

리스트의 요소인 [1, n] 에서 1은 \({\rm rad}(n)\) 으로 처음 값을 모두 1로 세팅한 것이다.

이제 다음과 같은 파이썬 코드를 보도록 하자.

 

for i in prime:
    for j in range(i, 11, i):
        result[j][0] *= i

코드에서 보듯이 10 이하의 각각의 소수들에 대해서 그 소수의 배수에 대해서는 1로 세팅된 \({\rm rad}(n)\) 에 그 소수를 곱해주는 형식으로 소인수들의 곱을 구해 나가는 것이다.

예를 들어, 소수 2에 대해서는 result 에 다음과 같은 변화가 생긴다.

[[1, 1], [2, 2], [1, 3], [2, 4], [1, 5], [2, 6], [1, 7], [2, 8], [1, 9], [2, 10]]

결국 2를 소인수로 갖게 되는 모든 \(n\) 들의 \({\rm rad}(n)\) 값들이 업데이트 된 것을 볼 수 있다. 이런식으로 소수 3에 대해서도 같은 과정을 거치면 result 는 다음과 같이 업데이트 된다.

[[1, 1], [2, 2], [3, 3], [2, 4], [1, 5], [6, 6], [1, 7], [2, 8], [3, 9], [2, 10]]

다시 소수 5에 대해서 같은 과정을 거치면

[[1, 1], [2, 2], [3, 3], [2, 4], [5, 5], [6, 6], [1, 7], [2, 8], [3, 9], [10, 10]]

마지막으로 소수 7에 대해서 같은 과정을 거치면

[[1, 1], [2, 2], [3, 3], [2, 4], [5, 5], [6, 6], [7, 7], [2, 8], [3, 9], [10, 10]]

이렇게 해서 최종적인 \({\rm rad}(n)\) 들을 얻을 수 있는 것이다.

위와 같은 과정을 \(n=100000\) 까지 실행한 후, \({\rm rad}(n)\) 을 기준으로 정렬을 하고, \({\rm rad}(n)\) 값이 같은 것들에 대해서는 다시 \(n\) 에 대해서 정렬하게 되면 쉽게 답을 구해낼 수 있다.