pn을 n번째 소수(2, 3, 5, 7, 11, ..), r을 (pn-1)n+(pn+1)n을 pn2으로 나눴을 때 나머지로 하자.
예를 들어, n이 3일 때, p3=5이고, 43+63=280은 5 mod 25와 합동이다.
나머지가 처음으로 109을 초과할 때 가장 작은 n의 값은 7037이다.
나머지가 처음으로 1010을 초과할 때 가장 작은 값을 구하시오.
--------------------------------------------------------------------------
이전 오일러 프로젝트 문제를 통해 소수와 나머지를 다루는 데 익숙해져 있으면 난이도 30%이지만 크게 어렵지 않게 해결 가능한 문제이다.
우선 충분한 크기의 소수 목록을 만들어 두고(천만 이하의 소수 목록을 만들어서 해결했는데, 결과론으로 보면 더 작은 목록을 만들어도 해결 가능했다), 각 소수에 대해 문제에서 제시한 공식을 대입해서 나머지 값을 구하면서 1010보다 큰 경우를 찾으면 된다.
앞에서 나온 나머지 문제를 해결할 때 중간값이 너무 커져서 에러가 발생한 경우를 봤기 때문에 부분계산을 할 때마다 나머지 연산을 적용해서 큰 수가 만들어지지 않게 하면서 답을 구했는데 생각보다 빠른 시간 내에 답을 구할 수 있었다.