日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問１１８「パンデジタル素数集合」
1 から 9 の全ての数字を使い, 自由につなげることで 10 進数の数字を作り,複数の集合を作ることができる.
集合 {2,5,47,89,631} は面白いことに全ての要素が素数である.
1 から 9 の数字をちょうど 1 個ずつ含み, 素数の要素しか含まない集合はいくつあるか?
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
私の回答例は以下の通りです。
def h(n): if n<2: return 0 if n<4: return n if (not n%2): return 0 for i in xrange(3, int(n**.5)+1, 2): if not n%i: return 0 return n def f(L, Lc=[], d=0, cnt=0): if d==9: return [], cnt+1 bk = Lc[:] for i in xrange(len(L)): Lc = bk[:] s = 0 for j in L[i:]: s = s*10 + j if Lc and Lc[0]<s: continue if h(s): Lc.insert(0, s) Lc, cnt = f(L[:i], Lc, d+len(L)-i, cnt) return Lc, cnt import itertools L0 = [i for i in xrange(1, 10)] v = 0 for t in itertools.permutations(L0): L, c = f(t) v += c print "cnt:", v
1から9までの数字の順列を発生させ、その１つひとつについて、素数だけの要素に分解していきます。
ただし、その分解できた要素の順番が異なっていても１つとして数えるため、要素が昇順に並んでいるパターンだけの件数を数えます。
総当たりですが１分ルールは守れるのでよしとします。
１．関数f(n)
・リストLの要素を左から素数で区切り、累積用リストLcに格納していきます。
dは確定した全要素の合計桁数で、cntは全素数要素のパターン数です。
最終的に必要な値は件数だけですが、この関数を回帰呼び出しで使えるようにするために、戻り値は累積用リストLcと求める件数とします。
・回帰呼び出しなので、最初は終了条件の記述が鉄則です。
確定した全要素の合計桁数が9ならば、1～9の数字の全部を使い切っていて、累積用リストLcに求めるパターンが格納されているので、空の累積用リストとカウンタcntを+1して戻ります。
・累積用リストLcのバックアップを取ります。
左から1桁ずつ区切って要素を確定していく中で、区切り方が条件に合わない場合に直前状態に戻すためです。
・for j in L[i:]: s = s*10 + j
位置iから右側を切り取り L[i:]とし、
jのforループ中で、1けたずつ取り出して10倍しながら足していき数値化しsとします。
・if Lc and Lc[0]<s: continue
重複を避けるため、全要素が昇順になる場合だけ採用し、それ以外は次へ。
・if h(s):
Lc.insert(0, s)
Lc, cnt = f(L[:i], Lc, d+len(L)-i, cnt)
関数hで数値sの素数判定します。
素数ならば、累積用リストLcに右から追加します。
そしてリストLの位置iから左側L[:i]について、当関数fを再起呼び出しして、さらに素数の要素があるか探索します。
２．関数h(n)・問１１１の素数判定を改良しました。
2未満に素数は無く、2と3は素数。ここまではif文で直接判定します。
その後は偶数を外し、3から先の奇数の倍数を外します。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
44680
