寻找完全数的智能算法

Question

有比O(N^2)更快的算法从样本1:N中找到完美的数字吗？或者有什么通用的速度改进来减少计算量？我知道，如果假设奇数不完美，我们可以从样本中删除奇数(未经证明，但我们可以在这里假设)。

Answer 1

下面是一种方法(num是您的号码)：

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")

编辑(学分：@cdlane)

默森素数和偶数完美数之间有一对一的对应关系。您可以使用这个事实通过Lucas-Lehmer素数测试生成Mersenne素数，并最终得到一个完美的数字：

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")

输出(使用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

Answer 2

您可以通过搜索Mersenne素数，而不是搜索完美数，从而获得显著的改进，然后输出它们的伴生完美数：

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

def is_odd_prime(number):
    """
    Efficiency of this doesn't matter as we're only using it to
    test primeness of exponents not the mersenne primes themselves
    """

    i = 3

    while i * i <= number:
        if number % i == 0:
            return False
        i += 2

    return True

print(6)  # to simplify code, treat first perfect number as a special case

for n in range(3, 5000, 2):  # generate up to M20, found in 1961
    if is_odd_prime(n) and lucas_lehmer_test(n):
        print(2**(n - 1) * (2**n - 1))

不是完美的，但远好于试图考虑数字寻找完美的数字。