プロジェクトオイラー問37

Problem 37 「切り詰め可能素数」 †

3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

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

一桁の素数から初めて素数という条件を見たいしながら左に伸ばしていきます。
その後左に伸ばしたものを右に縮めていくと考えます。
伸ばしたものを右から縮めていくとき一番右が2か5だと縮める前に割り切れてしまい素数ではありません。
よって一番右は3か7です。
伸ばしていくとき、伸ばしたものを右から縮めていくとき0,2,4,5,6,8だと割り切れるので
左右以外の桁は1,3,7,9以外ありえません。
また一番左は２，３、5,7以外では最後がうまくいきませんので２，３、5,7となります。
後はこれを全探索するだけです。
上限値を定めて両側探索すると少し早くなりそうです。


not_prime(N):-N<2,!.
not_prime(2):-!,fail.
not_prime(N):-N mod 2=:=0,!.
not_prime(N):-
      between(1,N,D),
      D1 is 2*D+1,
      (D1*D1>N->!,fail;true),
      N mod D1=:=0,
      !.
is_prime(N):-not(not_prime(N)).

search2(N,_,_):-
      not_prime(N),
      !,
      fail.
search2(N,Base,N1):-
      member(Left,[2,3,5,7]),
      N1 is Base*Left+N,
      is_prime(N1).

search2(N,Base,Result):-
      !,
      Base1 is Base*10,
      member(Left,[1,3,7,9]),
      N1 is Base*Left+N,
      search2(N1,Base1,Result).

check(N):-
      N<10,
      !,
      is_prime(N).
check(N):-
      is_prime(N),
      N1 is N//10,
      check(N1).

search(N):-
      member(Seed,[3,7]),
      search2(Seed,10,N),
      check(N).
sum([],0):-!.
sum([X|Xs],Result):-
      !,
      sum(Xs,Re),
      Result is Re+X.

main37:-
      findall(E,search(E),List),
      sum(List,Ans),
      write(Ans).