Project Euler 97

Problem 97
最初に知られた100万桁を超える素数は1999年に発見された。そしてそれは2^6972593-1というメルセンヌ素数である。2098960桁である。その後、さらに多くの桁数の2^p-1という形のメルセンヌ素数が見つかった。
しかしながら、2004年に2357207桁の巨大な非メルセンヌ素数が見つかった。それは、28433×2^7830457+1。
この素数の最後の10桁を求めよ。
http://projecteuler.net/index.php?section=problems&id=97

メルセンヌ数2ⁿ-1には、リュカテストという特別に速い素数判定法があるため、大きな素数はだいたいメルセンヌ素数ということになっている、という背景があります。

print (28433 * (1 << 7830457) + 1) % 10 ** 10

Pythonだとまともに計算しても答えが出てきてしまいます。
しかし、ここではべき乗を求めるごとに10¹⁰で割って、64ビットの範囲で計算できるようにしましょう。

def pow(n, e):
    if e == 0:
        return 1
    
    p = pow(n, e / 2)
    q = p * p % 10 ** 10
    if e % 2 == 1:
        return n * q % 10 ** 10
    else:
        return q

print (28433 * pow(2, 7830457) + 1) % 10 ** 10