프로젝트 오일러 69번

69번 문제는 다음과 같다.

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

n	Relatively Prime	φ(n)	n/φ(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

이 문제를 풀기 위해서는 Euler's phi (totient) function에 대해서 알아야 한다. 이 함수는 \(1\) 부터 \(n\) 까지의 양의 정수 중에 \(n\) 과 서로 소인 것의 개수를 나타내는 함수이다. 일반적으로 \(\phi (n)\) 으로 표기한다.  물론 이 문제를 풀기 위해서는 이 함수에 대해서 정확하게 이해하는 것이 중요하겠지만, 프로그래밍을 배우는 입장이라면 이 함수의 함수식이 다음과 같다는 것만 알면 된다. \[\phi (n)=n \cdot \prod \limits_{p} \left ( 1 - \dfrac{1}{p} \right ) \] \[ (단,\; n이 \; 소수이면\; \phi (n)=n-1) \]여기서 \(p\) 는 \(n\) 의 소인수가 된다. 이 함수식을 이용하여 문제를 해결 할 수 있다. 하지만 우리가 확인해야 하는 수가 \(2\) 부터 \(1000000\) 까지 무려 \(999999\) 개 이고, 컴퓨터가 아무리 빠른 계산을 한다고 하더라도 상당한 시간이 소요될 것이다.

수학문제를 풀면서 항상 중요하게 생각하는게 문제에서 요구하는 "구하라" 가 누구냐 하는 것이다. (그 구하라가 그 구하라가 맞나?) 이 문제에서 궁극적으로 요구하는 것은 \(\phi (n) \) 이 아니라 \( \dfrac{n}{\phi (n)}\) 이기 때문에 결과적으로는 \[\dfrac{n}{\phi (n)}=n \times \dfrac{1}{n \cdot \prod \limits_{p} \left ( 1-\dfrac{1}{p} \right )} =\prod \limits_{p} \dfrac{p}{p-1} \] \[ \left ( n 은 \;2 \le n \le 1000000 \; 인\; 자연수, \;p 는\; n \;의\; 소인수 \right ) \]의 최댓값을 구하는 문제가 된다.

여기에서 관심있게 봐야할 부분이 바로 \( \dfrac{p}{p-1}\) 이다. 이 값은 항상 \(1\) 보다 큰 값이다. 즉, 많이 곱해지면 곱해질수록 더 큰 값이 된다. 따라서 우리는 \(2 \le n \le 1000000\) 에서 가장 많은 소인수를 갖는 수를 찾아내면 된다. 최댓값이 \(1000000\) 이므로 가장 많은 소수를 갖기 위해서는 작은 소수부터 차례대로 곱해가면서 그 값이 \(1000000\)  이하가 되는 놈을 찾으면 된다.

참으로 어처구니 없게도 이 문제는 가장 작은 소수부터 차례대로 곱하되 그 곱이 \(1000000\) 이하가 될 때까지 곱하면 얼마가 되겠느냐를 묻는 문제가 된다. 이렇게 생각한다면 답을 눈 깜짝할 사이에 찾아 낼 수 있다.