「プロジェクトオイラー問７」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問７」(2014/02/12 (水) 16:45:48) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%207

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




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



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