프로젝트 오일러 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$ 에 대해서 정렬하게 되면 쉽게 답을 구해낼 수 있다.