Euler's Totient function, Φ(n) [sometimes called the phi function], is defined as the number of positive integers not exceeding n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than or equal to 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≤1000000 for which n/Φ(n) is a maximum.
오일러의 파이 함수(Totient function)인 Φ(n)은 n보다 크지 않고, n에 대해 상대적으로 소수인 양의 정수로 정의된다. 예를 들어, 1, 2, 4, 5, 7, 8은 9보다 작고, 9에 대해 상대적으로 소수이므로 Φ(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 |
위 표에서 보듯이 n이 10이하일 때, n/Φ(n)이 최대값인 것은 n=6인 경우이다.
n이 1백만 이하일 때, n/Φ(n)이 최대가 되는 값을 구하시오.
--------------------------------------------------------------------------
상대적으로 소수(relative prime)라는 표현이 재밌었는데, n을 (1일 제외하고) 나눌 수 없는 수로 이해했다. 8의 경우를 보면 8을 나눌 수 있는 2와, 2의 배수인 4, 6을 제외하고, 10의 경우에는 2의 배수인 2, 4, 6, 8과 5를 제외한 수가 된다.
처음에는 소수의 경우에는 n에서 1을 뺀 값(자신을 제외한 모든 수가 나눌 수 없으므로), 소수가 아닌 경우에는1~n-1까지 숫자 중 n을 나눌 수 있으면, 그 수의 배수까지 카운트해서 n에서 카운트한 값을 빼는 형태로 Φ(n)을 구했는데, 8에서 앞의 표가 다르게 Φ(n)=3이 나왔다. 원인을 찾아보니 2의 배수로 3을 카운트했는데(2, 4, 6), 1씩 더하면서 확인할 때 4도 8을 나눌 수 있는 숫자이므로 2번 카운트 된 것으로 분석되었다.
중복 계산되는 경우를 막기 위해, 간단하게 카운트를 통해 계산하는 방법을 포기하고, 매번 1~n-1까지 리스트를 만들고, n을 나눌 수 있는 숫자와 그 수의 배수를 리스트에서 삭제해 나가는 느리지만 정확하게 계산할 수 있는 방법으로 구현했다. 이번에도 처리속도가 문제였다. 짝수면 홀수만으로 리스트를 만드는 식으로 성능개선을 했지만, 큰 수가 나오면 느리긴 마찬가지였다.
가만히 관찰해보니 (자신을 제외하고 나눌 수 있는 수가 없으므로) 소수의 경우 Φ(n)이 커지고, n/Φ(n)은 작아지게 되어 있고, 해당되는 수의 (소수인) 약수가 많아질수록 n/Φ(n)이 커지고 있었다. 실행시간이 너무 길어져서 중간에 포기했지만, 최고값을 경신하는 경우는 2, 6, 30, 210, 2310, 30030이었는데 이것을 다시 보면 2, 2x3, 6x5, 30x7, 210x11, 2310x13으로 소수를 차례로 곱해가는 경우였다.
그래서, 백만보다 크지 않은, 연속된 소수의 곱을 구하니 답이 되었다.