프로젝트 오일러 97

메르센 수가 아닌 소수 의 마지막 10자리는?

문제 자세히 보기: [국어] [영어]

은 2백만 자리가 넘는 어마어마하게 큰 수지만, Java의 BigInteger를 이용하면 계산하지 못 할 것도 없다. 그러나 이 큰 수의 모든 자릿수가 필요한 게 아니라 마지막 10자리만 필요하므로 modPow를 쓰면 조금 쉽게 계산할 수 있을 것 같다.

(defn solve []
  (-> (.modPow (biginteger 2) (biginteger 7830457) (biginteger 10000000000))
      (.multiply (biginteger 28433))
      (.add (biginteger 1))
      (.mod (biginteger 10000000000))))

역시 예상대로 빠르게 답을 구한다.

p097=> (time (solve))
"Elapsed time: 0.477179 msecs"
873999??77

그런데, modPow를 쓰지 않고 그냥 무식하게 계산하면 어떨까?

(defn solve []
  (-> (.pow (biginteger 2) 7830457)
      (.multiply (biginteger 28433))
      (.add (biginteger 1))
      (.mod (biginteger 10000000000))))

위와 같이 modPow 대신 pow 메서드를 사용하도록 코드를 조금 수정해 실행해보면...

p097=> (time (solve))
"Elapsed time: 7.865695 msecs"
873999??77

modPow를 사용한 경우보다 거의 20배는 느려졌지만, 충분히 빠르게 답을 구한다.

참고

• 프로젝트 오일러 97 풀이 소스 코드