Python - Optimisation of Perfect Number search

Question

p = []
for x in range(1, 50000000):
    count = 0
    for y in range(1, x // 2 + 1):
        if (x % y == 0):
            count += y
    if (count == x):
        p.append(x)

This is my code to try and find all the perfect numbers that originate between 1 and 50000000. It works fine for the first 3 numbers, they are between 1 and 10000. But as it progresses it becomes extremely slow. Like maybe going through 1000 numbers every 10 seconds. Then eventually going through 10 numbers every 5 seconds.

Now is there anyway I could make this faster? I tried including some smaller things, like diving x by 2 to make sure we don't go over half (not going to be a multiple of x)

Answer 1

You can do a lot better. Consider the following:

1) Think of the factorization of 36 for example: 1x36, 2x18, 3x12, 4x9, 6x6. And that's it. Going further doesn't add anything new. The next factorization would be 9x4 but we already know that (4x9). This advantage gets progressively larger (compare the root of the last number you have to check against its half)

2) There are no odd perfect numbers. This is actually a conjecture (not proven yet) but they tried everything below 10^300 and didn't find any. So there are definately exactly none < 50000000. That means you can skip half the terms.

from math import ceil
p = []
for x in range(2, 50000000, 2):
    divisors = {1}
    for y in range(2, ceil(x**0.5) + 1):
        if x % y == 0:
            divisors.update({y, (x//y)})
    if sum(divisors) == x:
        print('-', x)
        p.append(x)
#- 6
#- 28
#- 496
#- 8128

This should be a lot faster but there are definately more things one can do.