Problem 21
友愛数ですね.友愛…
判定させるのを書いてみた.
def is_amicable(num): from math import sqrt k = 1 p = 1 for i in xrange(2,int(sqrt(num))+1): if not num % i: k += i if i != num / i: k += num / i if k == num: return False for i in xrange(2,int(sqrt(k))+1): if not k % i: p += i if i != k / i p += k / i if p == num: return True return False
10**4くらいなのでこれだけですぐ答えをえることは可能.ループで回してそれぞれが友愛数か判別してTrueなら加算で求まる.
それでいいんだけど,友愛数かどうか判別する時点で2つの数字が得られている.この時得られた片割れはループで調べる数に含まれている可能性が高いのでリストを用意して,得られた値をどんどん追加書きするという手を思いつく.で実際にやってみたところ下手すると遅くなった.うまくやれば速くはなった.でも頑張ったほど差が出るわけではないので却下.今回のループを回すので,
def amicable_pair(num): from math import sqrt k = 1 p = 1 for i in xrange(2,int(sqrt(num))+1): if not num % i: k += i if i != num / i k += num / i if k <= num: return 0 for i in xrange(2,int(sqrt(k))+1): if not k % i: p += i if i != k / i p += k / i if p == num: return k+num return 0
何かを用意して
print sum([amicable_pair(x) for x in xrange()])
とする方がお手軽に速くできて(効果はリスト並)楽チン.もし値が含まれているかどうかがわからないから嫌だ!っていう人は引数を2つにして,1つをループ内にあるかないかの判別式に使えば良いと思うよ!そもそもこの関数はこの問題用なところがあるからそんな汎用化を目指す意味が無い気がするけど….