Problem 97: 非メルセンヌ素数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 97. 非メルセンヌ素数

原文 Problem 97: Large non-Mersenne prime

問題の要約：2004年に見つかった非メルセンヌ素数は2,357,207桁の$28433 \times 2^{7830457}+1$であるがこの数の下10桁を求めよ

Pythonの整数はメモリのある限り桁数が無制限なので普通に計算しても答えが出てしまうのがすごいですが、ここはpow関数を使ってmoduloを指定すれば効率的に解くことが出来ます。

ちなみにメルセンヌ素数(Wikipedia)とは$2^n − 1$で表せる素数のことで、素数判定がしやすいので現在見つかっている巨大な素数の多くはメルセンヌ素数だそうです。

m = 10**10
print(f"Answer: {(28433*pow(2,7830457,m)+1)%m}")

（開発環境：Google Colab）