The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 26972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits.
However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1.
Find the last ten digits of this prime number.
1백만 자릿수가 넘는 소수 중 처음으로 알려진 소수가 1999년에 발견되었다. 이것은 26972593−1 형태인 메르센 소수(Mersenne prime)이다. 이 숫자는 2,098,960 자리로 구성된다. 마르센 소수 이후, 자릿수가 더 많은 2p−1 형태의 메르센 소수가 발견되고 있다.
그러나, 2004년에 2,357,207 자릿수인 큰 규모의 비 메르센 소수 28433×27830457+1이 발견되었다.
이 소수의 마지막 열 자릿수를 구하시오.
--------------------------------------------------------------------------
메르센 소수(Mersenne prime)라는 새로운 형태의 소수를 소개하고 그것을 응용하는 문제이다. 프로그래밍을 효율적으로 또는 어렵게 하는 데 수학이 필요하다는 것은 인정하지만, 갈수록 프로그래밍 보다는 수학을 공부하고 있는 것 같다.
파이썬의 정수 최대값 허용폭이 넓은 것을 믿고 정직하게 한 줄로 작성했더니 최대값을 넘어 동작하지 않는다는 에러가 나왔다.
문제에서 마지막 10자리 숫자를 물어봤고, 이것은 모든 숫자를 계산할 필요없이 마지막 10자리 숫자만 계산하면 되는 것이었다. 그래서 % 연산자를 이용해 계속 10자리만 남게 하면서 2를 계속 곱해 27830457을 구하고, 거기에 28433곱하고 1을 더해서 나온 숫자의 마지막 10자리만 뽑아내면 되므로 문제를 해결하는 것은 그리 까다롭지 않았다.