The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form ; it contains exactly digits. Subsequently other Mersenne primes, of the form , have been found which contain more digits.
However, in 2004 there was found a massive non-Mersenne prime which contains digits: .
Find the last ten digits of this prime number.
gmpy library makes this problem trivial. Using
gmpy, this code takes about half a second to run. Without
gmpy, well, let’s just say it takes considerably more than a minute to run.
If you’re dealing with large numbers in Python, I highly recommend
#!/usr/bin/env python from gmpy2 import mpz print(str(mpz(28433*2**7830457+1))[-10:])
$ time python3 non-mersenne.py real 0m0.358s user 0m0.308s sys 0m0.012s