Project Euler #23 efficiency

I am trying to write a program in python to answer the following problem:

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.

So here is my code which should theoretically work but which is way too slow.

import math
import time

l = 28123

abondant =
def listNumbers():
for i in range(1, l):
s = 0
for k in range(1, int(i / 2) + 1):
if i % k == 0:
s += k
if s > i:
abondant.append(i)

def check(nb):
for a in abondant:
for b in abondant:
if a + b == nb:
return False
return True

def main():
abondant_sum = 0
for i in range(12, l):
if check(i):
abondant_sum += i
return abondant_sum

start = time.time()
listNumbers()
print(main())
end = time.time()
print("le programme a mis ", end - start, " ms")


How can I make my program more efficient?

for a in abondant: return nb-a not in abondant

3 Answers
3

The thing is that you make a double iteration on "abondant" in the check function that you call 28111 times.
It would be much more efficient to only compute a set of all a+b once and then check if your number is inside.

Something like:

def get_combinations():
return set(a+b for a in abondant for b in abondant)


And then maybe for the main function:

def main():
combinations = get_combinations()
non_abondant = filter(lambda nb: nb not in combinations, range(12,l))
return sum(non_abondant)


Checking until half and summing up all passing numbers is very inefficient.

Try to change

for k in range(1, int(i / 2) + 1):
if i % k == 0:
s += k


to

for k in range(1, int(i**0.5)+1):
if i % k == 0:
s += k
if k != i//k:
s += i//k


Once you have the list of abundant number you can make a list result = [False] * 28123 and then

result = [False] * 28123

for a in abondant:
for b in abondant:
result[min(a+b, 28123)] = True


Then

l =
for i in range(len(result)):
if not result[i]:
l.append(i)
print(l)


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.