しかし, 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).
最終更新:2014年03月04日 10:49