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


Problem 58 「螺旋素数」 †

らせん状に数字を生成した時対角線上の数字の素数の割合をこたえる問題。
詳細はリンク先を参照のこと


解法
書くだけ問題。
ほとんどの計算時間が素数判定に費やされているので、そこを多少改善できますが。
それくらいです。


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


search(Hit,Bad,N,Size,0):-
	Size>3,
	Hit1 is Hit*10,
	All is Hit+Bad,
	Hit1<All,
	!,
	Size1 is Size-2,
	write([N,Hit,Bad]),
	write([ans,Size1]).
search(Hit,Bad,N,Size,3):-
	!,
 	N1 is N+Size+1,
 	Size1 is Size+2,
	Bad1 is Bad+1,
	search(Hit,Bad1,N1,Size1,0).
search(Hit,Bad,N,Size,P):-
	is_prime(N),
	!,
 	Hit1 is Hit+1,
	N1 is N+Size-1,
	P1 is P+1,
	search(Hit1,Bad,N1,Size,P1).
search(Hit,Bad,N,Size,P):-
	!,
	N1 is N+Size-1,
 	Bad1 is Bad+1,
	P1 is P+1,
	search(Hit,Bad1,N1,Size,P1).


main58:-search(0,1,3,3,0).