Project Euler Problem 021
http://projecteuler.net/index.php?section=problems&id=21
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers. For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220. Evaluate the sum of all the amicable numbers under 10000.
10000以下の友愛数の合計を求める。
約数の和は素因数分解して各素因数の階乗の和ごとの積で出せるけど、下のコードのように単純に約数を計算する方が早かった。
import math import datetime def divisor(n): if n == 0: return [ ] if n == 1: return [1] a = [1, n] limit = math.sqrt(n) for i in xrange(2, int(limit)+1): if n % i == 0: a.append(i) if limit != i: a.append(n/i) a.sort() return a def d(n): return sum(divisor(n)[0:-1]) def euler021(): result = 0 check = set() for x in xrange(1, 10000): if x in check: continue n = d(x) m = d(n) if n != m and x == m: print (n, m) result += n + m check.add(n) print result begin = datetime.datetime.now() euler021() end = datetime.datetime.now() print end - begin
答え: 31626
実行時間: 0.292657秒くらい