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