Project Euler - Probrem 47

Project Euler(プロジェクト　オイラー）の問題をpythonでやってみます。

出典： Project Euler（日本語 翻訳サイト）
　　　ProjectEuler.net（英語サイト）

Problem 47
連続する2つの数がそれぞれ2つの異なる素因数を持つのは

• 14 = 2 × 7
• 15 = 3 × 5の場合である.

同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは

• 644 = 22 × 7 × 23
• 645 = 3 × 5 × 43
• 646 = 2 × 17 × 19の場合である.

連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え, 連続する数の中で最小のものを答えよ.

－－－－－

私の解答例は以下です。畳んでいます。

def p(n):
	L = [0,0]+[1]*(n-1)
	i = 2
	while i*i<=n:
		while not L[i]: i += 1
		for j in xrange(i+i, n+1, i): L[j] = 0
		i += 1
	return [i for i in xrange(n+1) if L[i]]

def g(n, P):
	s, d = n, {}
	for i in P:
		while s>=i:
			if s%i: break
			else:
				while not s%i:
					d[i], s = d.get(i, 0)+1, s//i
		if s<i: break
	return d

def f(n):
	P = p(10000000)
	i, L = 0, []
	while True:
		i += 1
		s = g(i, P)
		if len(s)==n: L.append(s)
		else: L = []
		if len(L)==n: break
	return L

n = 4
for d in f(n):
	s = 1
	for k, v in d.items():
		s *= k**v
	print s, sorted(d.items())

３つの関数を使っています。

１．関数p(n)
・n以下の素数リストを返します。problem37と同じです。
２．関数g(n, P)
・素数リストPに含まれる素数にて、nを素因数分解した辞書を返します。
　キーが素数で値がその素数が含まれる数です。

・s, d = n, {}
　sを素数で割り算していきます。初期値はnです。
　dは返却用の辞書です。初期値は空の辞書です。

・for i in P:
　素数リストPの要素を1つずつループ変数iとします。

・while s>=i:
　割られる数sが割る数の素数i以下の場合に割り算をしていきます。

・if s%i: break
　%は割り算の余りです。余りがある（論理的にTrueの）場合、割る数iを次の値に進めます。

・else:
　　while not s%i:
　　　d[i], s = d.get(i, 0)+1, s//i
　余りがない（論理的にFalseの)場合、割り切れなくなるまで、割る数iで割り続けます。
　辞書dのキーiの値を1ずつカウントアップします。
　割られる数sはiで割った商を設定します。

・if s<i: break
　割られる数sよりも割る数の素数iが大きくなったら終了します。

３．関数f(n)
・n個の素因数をもつ連続するn個の数について、その連続するそれぞれの値を素因数分解した辞書を要素とするリストを返します。

・P = p(10000000)
　リストPは1000万以下の素数の表です。
　これは私の手持ちの素数発生関数で１分ルールとメモリを満たす限界です。
　素因数分解をするときに割る数として使用します。

・i, L = 0, []
　iはカウンターで、Lは戻り値用リストです。、

・while True:
　　i += 1
　無限ループです。ループの都度、カウンターiを1つカウントアップします。

・s = g(i, P)
　sはカウンター値iを素数表Pを使って素因数分解した辞書です。

・if len(s)==n: L.append(s)
　else: L = []
　len関数の辞書sを渡すと、辞書sのキー件数を返します。
　この辞書sのキー件数は素因数の数なので、n個の場合、戻り値用リストLにためます。
　n以外の場合、戻り値用リストLをクリアします。

・if len(L)==n: break
　戻り値用リストLの件数をチェックし、要素数がnならばループ終了です。

３．関数の外
・問題に合う値を表示します。

・n = 4
　for d in f(n):
　問題に合うように引数を4を関数fに渡します。

・s = 1
　　for k, v in d.items():
　　　s *= k**v
　　print s, sorted(d.items())
　問題に合う連続する数をsとして、素因数とその掛け合わせる数に基づいて、再現します。
　辞書d.itmes()は、辞書dのキーと値の組のタプルを返します。
　ここではそれぞれループ変数kにキー値を、ループ変数vに値を設定しています。
　**演算子は累乗です。ここではkのv乗値をsに掛け算で累積しています。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
134043 [(3, 1), (7, 1), (13, 1), (491, 1)]
134044 [(2, 2), (23, 1), (31, 1), (47, 1)]
134045 [(5, 1), (17, 1), (19, 1), (83, 1)]
134046 [(2, 1), (3, 2), (11, 1), (677, 1)]