# Project Euler Solution 97: Large non-Mersenne prime

In Problem 97: Large non-Mersenne prime we are to find the last digits of a very large prime number.

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form $2^{6972593}−1$; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form $2^p−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\times2^7830457+1$.

Find the last ten digits of this prime number.

This is again straightforward in Python using the arbitrary large integers:

def solution_naive() -> int:
return (28433 * 2**7830457 + 1) % 10**10


If we wouldn't have these, we could use a modulus operation after each multiplication. We are only interested in the lower 10 digits, so we don't need to track the higher digits at all.

def solution_modulus() -> int:
divisor = 10**10
number = 28433
for i in range(7830457):
number *= 2
number %= divisor
number += 1
number %= divisor
return number


The curious thing is that the naive solution takes 43.568 ms whereas the modulus solution takes 795.617. It seems to be more efficient for Python to use the large integers with more and more multiplications than to use a modulus operation after every tun.