プロジェクトオイラー問26 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2026
Problem 26 「逆数の循環節 その1」 †
自然数1<ｎ<1000とし1/nで循環節が最も長くなるものを求めよ。
素数ｎ以外調べる必要がないのでそれだけ調べます。
999でなくn=２～99999まで全部調べても4秒。

not_prime(N):-N<2.
not_prime(N):-
	between(2,N,D),
	(N<D^2 ->!,fail;N mod D=:=0),
	!.
is_prime(N):-not(not_prime(N)).

divs(N,Div,N):-N mod Div>0,!.
divs(N,Div,Result):-
	N1 is N//Div,
	!,
	divs(N1,Div,Result).

div2And5(N):-
	divs(N,2,N1),
	divs(N1,5,N2),
	N2=:=1.

calcOK(N):-not(div2And5(N)).



yakusu(N,Div,[]):-
	Div^2 > N,
	!.
yakusu(N,Div,[Div,Div2|Result]):-
	N mod Div=:=0,
	!,
	Div1 is Div+1,
	Div2 is N // Div,
	yakusu(N,Div1,Result).
yakusu(N,Div,Result):-
	!,
	Div1 is Div+1,
	yakusu(N,Div1,Result).




mod_pow(0,_,_,1):-!.
mod_pow(0,_,_,_):-!,fail.
mod_pow(X,N,Pow,Mult):-
	X mod 2=:=1,
	!,
	Mult1 is (Mult*Pow) mod N,
	X1 is X//2,
	Pow1 is (Pow^2) mod N,
	mod_pow(X1,N,Pow1,Mult1).
mod_pow(X,N,Pow,Mult):-
	!,
	X1 is X//2,
	Pow1 is (Pow^2) mod N,
	mod_pow(X1,N,Pow1,Mult).

search([X|_],N,X):-
	mod_pow(X,N,10,1),
	!.
search([_|Xs],N,Result):-
	!,
	search(Xs,N,Result).

calc(N,[Result,N]):-
	calcOK(N),
	is_prime(N),
	N1 is N-1,
	yakusu(N1,1,List),
	sort(List,List1),
	search(List1,N,Result).

search(E):-
	between(1,999,N),
	calc(N,E).
main:-
	findall(E,search(E),Es),
	sort(Es,Es1),
	reverse(Es1,[Ans|_]),
	write(Ans).