26 de julio de 2012

Project Euler 23


#!/usr/bin/env python
#reused from problem 21
def sumdiv(n):
    s=1
    p=2
    while p*p<=n and n>1:
        if n%p==0:
            j=p*p
            n/=p
            while n%p==0:
                j*=p
                n/=p
            s*=(j-1)
            s/=(p-1)
        if p==2:
            p=3
        else:
            p+=2
    if n>1:
        s*=(n+1)
    return s
#reused from problem 21
def d(n):
    return sumdiv(n)-n
def abundant(n):
    return n<d(n)
r=set(x for x in xrange(1,20162) if abundant(x))
#The 2 following lines are the supposed
#to be the same line, just broken in 2 parts
#to fit in the blog.
s=sum(x for x in xrange(1,20162)
     if not any(x-a in r for a in r))
print s
I used set, because it's "in" is way faster than list's "in".