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

プロジェクトオイラー問49」(2014/02/18 (火) 08:44:48) の最新版変更点

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

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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2049 *Problem 49 「素数数列」 † 項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ. (i)3つの項はそれぞれ素数である. (ii)各項は他の項の置換で表される. 1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが, 4桁の増加列にはもう1つ存在する. それではこの数列の3つの項を連結した12桁の数を求めよ. 解法 まずa1<=a2<=a3<=a4でa1~a4は0~9の数という条件を満たす [a1,a2,a3,a4]というリストを全探索する。 ある[a1,a2,a3,a4]を並べ替えたものを4桁の整数とみて、これが素数であるか判定し 素数のリストを得る。 その中から素数2つを得て、n=差分*2+小さいほうの素数 が素数のリストにありかつnが一番大きな数であるならそれを答えとする。 計算量は2万回以下。 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)). seed(0,_,[]):-!. seed(Keta,P,[P|Xs]):- Keta1 is Keta-1, seed(Keta1,P,Xs). seed(Keta,P,Xs):- P<9, !, P1 is P+1, seed(Keta,P1,Xs). seed_w(Perm):- seed(4,0,Perm), sum(Perm,A), A mod 3>0. sum([],0):-!. sum([X|Xs],Result):-!,sum(Xs,Re),Result is Re+X. perm([],0):-!. perm(Xs,Result):- select(X,Xs,Xs1), perm(Xs1,Re), Result is Re*10+X. perm_w(Xs,Result):- perm(Xs,Result), Result>999, is_prime(Result). main49:-seed_w(Seed), findall(Perm1,perm_w(Seed,Perm1),Ps), sort(Ps,Perms), member(N1,Perms), member(N2,Perms), N1<N2, N3 is 2*(N2-N1)+N1, N2<N3, member(N3,Perms), write([N1,N2,N3]), fail.

表示オプション

横に並べて表示:
変化行の前後のみ表示: