Project Euler 23

問題

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28 であるので, 28は完全数である.

真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.

12は, 1 + 2 + 3 + 4 + 6 = 16 となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.

2つの過剰数の和で書き表せない正の整数の総和を求めよ.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2023

回答

辞書内包表記の練習。
※辞書内包表記を使う理由：
適当に見たサイトから
http://www.peignot.net/python-speed

setsや辞書を使った要素の検証（O(1)）は、配列の検索（O(n)）よりも高速です。 a in b を調べるとき、bはリストやタプルではなくsetsや辞書であるべきです。

# -*- coding: utf_8 -*-
def factor_sum_seq(max):
  dl = [0] + [1]*(max)
  seq = range(max+1) 
  for i in seq[2:]:
    for j in seq[i*2::i]:
      dl[j] += i
  return dl

def cof():
  MAX = 28123+1 #+1を計算するのすらめんどい

  seq = range(MAX)
  dl = factor_sum_seq(MAX)
  abu = [i for i in seq if dl[i] > i and dl[i]<MAX]
  abu2 = {i+j:True for i in abu for j in abu}
  ans = 0
  for i in seq:
    if not (i in abu2):
      ans += i
  print ans

cof()

それにしても遅すぎる。とはいっても改善するつもりも全くないのだけど。