2012年6月22日金曜日

プロジェクトオイラー Problem21

「プロジェクト オイラー」の問題をpythonでやってみます。

出典:
Project Euler(日本語翻訳サイト)
参考:
サイエンスもの置き場 プロジェクトオイラーを遊び倒すガイド(初級編)

Problem 21
d(n)をnの真の約数の和と定義する。(真の約数とはn以外の約数のことである。)
もし、d(a) = b かつ d(b) = a (a ≠ b)を満たすとき、aとbは友愛数(親和数)であるという。

例えば、220の約数は1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110なので
d(220) = 284である。
また、284の約数は1, 2, 4, 71, 142なので

d(284) = 220である。

それでは10000未満の友愛数の合計を求めよ。


私の解答例は以下です。
-----

def d(n):
	L = []
	for i in xrange(1, n):
		if n%i: continue
		elif n<i*i: break
		L.append(i)
		if 1<i<n/i: L.append(n/i)
	return sum(L)
	
def f(n):
	L = []
	for i in xrange(1, n):
		s = d(i)
		t = d(s)
		if i!=s and i==t: L.append(s)
	return L
	
L = f(10000)
print sum(L)
print L
-----

2つの関数を使用しています。
1.d(n)
・nの真の約数の合計値を返します。
・リストLに約数をためていき、関数終了時にsum関数でリストLの要素の合計値を返します。
・for i in xrange(1, n):
 真の約数はnを含まないので、ループ変数iは1からn-1までの値とします。
・if n%i: continue
 %演算子は割り算の余りです。論理式では0がFalse、1以上の値がTrueです。
 iで割って余りがあれば約数ではないので、ループ変数iは次の値に進みます。
・elif n<i*i: break
 割る数iがnの約数のとき、商n/iも約数です。割る数と商の両方を約数リストにためていけば、割る数が商よりも小さい場合だけ試せば十分です。
 割る数iは2乗してnになる値を超えると割る数よりも商が小さくなり、割る数と商が入れ替わっただけの、もうすでに試した数になるためループは終了します。
・L.append(i)
 if 1<i<n/i: L.append(n/i)
 割る数iは無条件で約数リストLに追加し、商n/iはチェックして約数リストLに追加します。
 i=1の場合、n/iはnになり、自分自身を含まないという「真の約数」の定義に合わないので追加しません。
 i=i/nの場合、割る数iを直前行で約数リストに追加しているのでn/iは追加しません。


2.f(n)
・n未満の友愛数のリストを返します。
・for i in xrange(1, n):
 真の約数はnを含まないので、ループ変数iは1からn-1までの値です。
・s = d(i)
 t = d(s)
 sはループ変数iの「真の約数」の和で、tはこのsの「真の約数」の和です。
・if i!=s and i==t: L.append(s)
 iとsが異なる値であり、iとtが同じ値であることは友愛数の定義です。



解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
31626

[284, 220, 1210, 1184, 2924, 2620, 5564, 5020, 6368, 6232]

(追記)
・20120715
 ソースコード部分にSyntaxHighlighterを導入。

0 件のコメント:

コメントを投稿