Project Euler Problem 023

http://projecteuler.net/index.php?section=problems&id=23
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2023

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number.
For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28,
  which means that 28 is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n
  and it is called abundant if this sum exceeds n.
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16,
the smallest number that can be written as the sum of two abundant numbers is 24.
By mathematical analysis, it can be shown that all integers greater than 28123 can be written
  as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis
  even though it is known that the greatest number
  that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

過剰数 + 過剰数で表せない数の総計。問題から 28123以上の数は表せることが分かるので、それ未満の数について調べる。
よく分からなかったので、とりあえず過剰数の集合を求めて、その後Greedyにひとつずつ調べた。調べたい数から任意の過剰数を引いた数が過剰数であれば過剰数の和で表す事ができる(=足し算しない)

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)
    return a


def euler023():
    N = 28123
    
    abundant = set( i for i in xrange(12, N+1) if i + i < sum(divisor(i)) )
    
    result = 0
    for i in xrange(1, N+1):
        for j in abundant:
            
            if j > (i / 2):
                result += i
                break
            
            if (i-j) in abundant:
                break
        
        else:
            result += i
        
    print result


begin = datetime.datetime.now()
euler023()
end = datetime.datetime.now()
print end - begin

答え: 4179871
実行時間: 1.710660秒くらい

他に格好いいやり方がありそうやけど、調べるの忘れてた。まぁ、そのうちに。