Smart algorithm for finding perfect numbers

Question

Is there an algorithm that is quicker than O(N^2) for finding perfect numbers from a sample 1:N? Or any general speed improvements to do less computation? I know we can remove odd numbers from the sample if we assume they are not perfect (unproven but we can assume it here regardless).

Answer 1

Here is a way to do it (num is your number):

if sum(i for i in range (1, num) if num % i == 0) == num:
    print(num, "is a perfect number")
else:
    print(num, "is not a perfect number")

EDIT (credits: @cdlane)

There is a one-to-one correspondence between the Mersenne primes and the even perfect numbers. You can use this fact to generate Mersenne primes with the Lucas–Lehmer primality test and get eventually a perfect number:

def lucas_lehmer(p):
    s = 4
    m = 2 ** p - 1
    for _ in range(p - 2):
        s = ((s * s) - 2) % m
    return s == 0

def is_prime(number):
    if number % 2 == 0:
        return number == 2
    i = 3
    while i * i <= number:
        if number % i == 0:
            return False
        i += 2
    return True

for num in range(3, N, 2):
    if is_prime(num) and lucas_lehmer(num):
        print(2 ** (num - 1) * (2 ** num - 1), "is a perfect number")

Output (with N=500):

28 is a perfect number
496 is a perfect number
8128 is a perfect number
33550336 is a perfect number
8589869056 is a perfect number
137438691328 is a perfect number
2305843008139952128 is a perfect number
2658455991569831744654692615953842176 is a perfect number
191561942608236107294793378084303638130997321548169216 is a perfect number
13164036458569648337239753460458722910223472318386943117783728128 is a perfect number
14474011154664524427946373126085988481573677491474835889066354349131199152128 is a perfect number