Problem #23

Worked on Project Euler Prob­lem #23 last night. I was suc­cess­ful, though my brute force approach was less than speedy. Below is the not so pretty code. First, all abun­dant num­bers below 28123 are found and appended to a list. Next, pos­i­tive inte­gers between 1 and 28123 that can not be the sum of two abun­dant num­bers are found. These inte­gers are marked as “valid.” The final step is to sum the valid inte­gers and print the result.

I’m cer­tainly curi­ous as to meth­ods that can improve this task.

#!/usr/bin/python

abun­dant = []
valid = []

def con­tains(list, value):
    try:
        idx=list.index(value)
    except Val­ueEr­ror:
        idx=-1
    return idx

for x in range(2,28123):
    sum = 1
    for n in range(2,x/2+1):
        if x % n == 0:
            sum += n
    if sum > x:
        abun­dant.append(x)

for num in range(1,28123):
    bad_number = False
    for j in abun­dant:
        if num-j < 0:
            con­tinue
        if con­tains(abun­dant, num-j) > -1:
            bad_number = True; break
               
    if not bad_number:
        valid.append(num)
        print “Valid: “+str(num)

sum = 0
for num in valid:
    sum += num
print str(sum)

Leave a Reply