「プロジェクトオイラー問97」の編集履歴(バックアップ)一覧はこちら

プロジェクトオイラー問97」(2014/03/04 (火) 10:49:28) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2097 Problem 97 「大きな非メルセンヌ素数」 † 100万桁を超える初めての素数は1999年に発見された. これはメルセンヌ素数であり, 2^6972593-1 である. 実際, 2,098,960桁ある. それ以降も, より多くの桁になるメルセンヌ素数 (2p-1の形の数) が他にも発見されている. しかし, 2004年に, 非常に大きな非メルセンヌ素数が発見された. これは2,357,207桁の数であり, 28433×2^7830457+1である. この素数の末尾10桁を答えよ. 解法 モード演算の中で計算すれば高速に求まります。 まあPrologなんで2^7830457+1を直接求めてもいいんですけれどね。 好みの問題です。 mod_pow(_,0,Result,Result):-!. mod_pow(Pow2,R,Mult,Result):- R mod 2=:=0, !, R1 is R//2, Pow22 is (Pow2*Pow2) mod 10^10, mod_pow(Pow22,R1,Mult,Result). mod_pow(Pow2,R,Mult,Result):- !, R1 is R//2, Mult1 is (Mult*Pow2) mod 10^10, Pow22 is (Pow2*Pow2) mod 10^10, mod_pow(Pow22,R1,Mult1,Result). main97:- mod_pow(2,7830457,1,T), T1 is (T*28433+1) mod 10^10, write(T1).

表示オプション

横に並べて表示:
変化行の前後のみ表示: