※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


Problem 7 「10001番目の素数」 †

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10001 番目の素数を求めよ.




基本はsqrt(N)まで試し割って割り切れる数が見つかればその数は素数でない。
でなければ素数と判定します。
本当や1以下の取り扱いや2や素の倍数の判定が必要ですが、問題の性質から奇数だけを考えてコードをくみます。



not_prime(N):-
	between(1,N,N1),
	Div is N1*2+1,
	(Div*Div>N->!,fail;true),
	N mod Div=:=0,
	!.

is_prime(N):-not(not_prime(N)).

search(Stop,Stop,_,Ans,Ans):-!.
search(Count,Stop,P,_,Result):-
	is_prime(P),
 	!,
	P1 is P+2,
	Count1 is Count+1,
	search(Count1,Stop,P1,P,Result).
search(Count,Stop,P,TempAns,Result):-
	!,
 	P1 is P+2,
	search(Count,Stop,P1,TempAns,Result).

main7:-
	search(1,10001,3,3,Ans),write(Ans).