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).
最終更新:2014年02月12日 16:45