プロジェクトオイラー 問１２４

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１２４「順序付き根基」
n の"根基"(radical)は, rad(n) で表し, n の素因数の積を意味する.
例えば 504 = 23 × 32 × 7 であるから, rad(504) = 2 × 3 × 7 = 42 である.
1 ≦ n ≦ 10 に対して rad(n) を計算し, rad(n) を対象にソートし, rad(n) が同じ場合は n を対象にソートすると以下のようになる.

未ソート 　 ソート済み
 n rad(n) n rad(n) k
 1  1     1  1     1
 2  2     2  2     2
 3  3     4  2     3
 4  2     8  2     4
 5  5     3  3     5
 6  6     9  3     6
 7  7     5  5     7
 8  2     6  6     8
 9  3     7  7     9
10 10    10 10    10

E(k) をソートした表の n の列の k 番目の要素とする.
例えば, E(4) = 8, E(6) = 9 である.

rad(n) を 1 ≦ n ≦ 100000 でソートした場合, E(10000) を求めよ.



注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。



私の回答例は以下の通りです。

def f(nmin, nmax, k):
	P = p(nmax)
	E = []
	for n in xrange(nmin, nmax + 1):
		if n < 1: continue
		L = [1]
		m = n
		for i in P:
			if m % i == 0:
				L.append(i)
				while m % i == 0: m //= i
			if m == 1: break
			
		r = mul(L)
		E.append((r, n, L[1:]))
		
	Es = sorted(E)
	return Es[k-1]

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 mul(L): return reduce(lambda x,y:x*y, L)

if __name__=="__main__":
	nmin, nmax, k = 1, 100000, 10000
	r, n, L = f(nmin, nmax, k)
	print nmin, "≦ n ≦", nmax, "のとき、E(", k, ") =", n
	print "rad(", n, ") =", " x ".join([str(i) for i in L]), "=", r 

１．関数f(nmin, nmax, k)
・nの最小値と最大値、問題で求めるk番目として指定するkを受け取り、
　E(k)をソートした表の、k番目の(根基r, n, nの素数リスト)のタプルを返します。

・P = p(nmax)
　Pは必要な素数のリストです。nmax以下の素数が小さい順に入っています。

・for n in xrange(nmin, nmax + 1):
　ループ変数nは、nmimからnmaxまで１つずつ大きくしながら処理します。

・if n < 1: continue
　nが1未満は処理対象外なので処理せず次のnへ進みます。
 
・L = [1]
　Lはnを構成する素因数リストです。
　根基の計算の掛け算のため、1を設定して初期化しておきます

・m = n
　mはnを素因数で割った商です。素因数が判明する都度、値が変化します。

・for i in P:
　ループ変数iは素因数リストPから小さい順に取り出した値です。

・if m % i == 0:
　　L.append(i)
　　while m % i == 0: m //= i
　mが素数iで割り切れる場合、素因数リストLに追加し、mを素因数iで割れるだけ割り込んでおきます。

・if m == 1: break
　mが1になれば素因数分解の終了で、素数iのループを終了します。

・r = mul(L)
　rはnの根基です。関数mulで素数リストLの全要素の積を求めます。
 
・E.append((r, n, L[1:]))
　Eは、(nの根基r, n, nの素因数リストL)のタプルをためるリストです。
 
・Es = sorted(E)
　Esは上記Eに求める範囲のタプルをため終わったところで、ソートします。
　ソートキーは、指定しない場合は先頭からになるので、
　この場合、根基r、nの順にソートキーとして採用されます

・return Es[k-1]
　求めるk番目の値は、ソート済リストEsのインデックスk-1番目の値です。

２．関数P(n)
・n以下の素数を小さい順にもつリストを返します。問３７で作成した関数を流用しました。

３．関数mul(L)
・リストLの全要素の積を返します。問１１０で作成した関数を流用しました。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
1 ≦ n ≦ 100000 のとき、E( 10000 ) = 21417
rad( 21417 ) = 3 x 11 x 59 = 1947