프로젝트 오일러 123번

Let \(p_n\) be the \(n\)th prime : \(2,\; 3,\; 5,\; 7,\; 11,\; \cdots,\) and let \(r\) be the remainder when \((p_n -1)^n + (p_n +1)^n\) is divided by \(p_n ^2\).

For example, when \(n=3, \; p_3 = 5\), and \(4^3 + 6^3 = 280 \equiv 5\) mod \(25\).

The least value of \(n\) for which the remainder first exceeds \(10^9\) is \(7037\).

Find the least value of \(n\) for which the remainder first exceeds \(10^{10}\).

---

\(p_n\) 이 \(2, \; 3, \;5, \;7, \; 11, \; \cdots\) 에서 \(n\) 번째 소수를 나타낸다고 하자. 또한 \(r\) 은 \((p_n -1 )^n + (p_n +1)^n\) 을 \(p_n ^2\) 으로 나눈 나머지라고 하자.

예를 들어, \(n=3\) 이면 \(p_n = 5\) 가 되고, \((5-1)^3 + (5+1)^3\) 을 \(5^2\) 으로 나눈 나머지는 \(5\)가 된다. 

이런식으로 나머지를 계산해 나갈 때, 처음으로 나머지가 \(10^9\) 을 넘게 되는 \(n\) 은 \(7037\) 이 된다.

처음으로 나머지 \(r\) 가 \(10^{10}\) 을 넘게 되는 \(n\) 의 값을 구하시오.  

이 문제를 쉽게 풀기 위해서는 120번 문제의 두 번째 풀이법을 알고 있어야 한다.

120번 문제에 따르면 \((p_n -1)^n + (p_n +1)^n\) 을 \(p_n ^2\) 으로 나눈 나머지는 \(n\) 이 짝수일 때는 \(2\) 가 되고, \(n\) 이 홀수일 때는 \(2\times n \times p_n\) 을 \(p_n ^2\) 으로 나눈 나머지와 같다. 

따라서 이 문제는 소수들의 리스트를 먼저 만든 다음, \(n = 7039\) 부터 \(2\) 씩 증가시면서 \( 2 \times n \times p_n\) 을 \(p_n ^2\) 으로 나눈 나머지들만 살펴보면 된다.

빠른 시간 내에 답을 구할 수 있을 것이다.