프로젝트 오일러 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$ 으로 나눈 나머지들만 살펴보면 된다.

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