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).

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2014年03月04日 10:49