python - 完美数字代码的效率（Python）

Question

n = int(input())
sum1 = 0
for i in range(1, n//2  + 1):
    if(n % i == 0):
        sum1 = sum1 + i
if (sum1 == n):
    print("YES")
else:
    print("NO")

这是我在 python 中检查数字是否完美的代码，它给出了正确的输出，但是当我尝试在网站上提交它（codechef）时，我得到了超时。我怎样才能提高效率？

错误是：

状态：超过时间限制

标签： pythonperformance

Answer 1

正如@hivert 指出的那样，下面的解决方案假设完美数字是偶数。事实上，不知道是否存在奇完美数，但是有很多信息表明不存在奇完美数。（https://en.wikipedia.org/wiki/Perfect_number#Odd_perfect_numbers）。

首先，我们必须有N > 10 ¹⁵⁰⁰。有了这个，我们将继续处理偶数情况。

如果偶数具有以下形式，则它是完美的：

2 ^{p - 1} * (2 ^p - 1)，其中 p 是梅森素数。

我们需要一个方便的质数检查器来有效地执行此操作。幸运的是，这是一个非常流行的话题，并且有很多现有的功能可以做到这一点。例如，@Alexandru 的答案提供了如何创建最紧凑的映射 n → isprime(n) 到极限 N？是一个非常好的和直接的 python 实现。但是，如果我们追求纯粹的速度，我们将需要采用替代方法，例如米勒拉宾。这在图书馆sympy中提供

这是我们非常高效的完美偶数检查器：

from sympy.ntheory import isprime
 
def IsPerfect(N):
    ## First get the number of 2's that divide N
    ## If there are none, the number is not perfect
 
    p = 0
 
    while N % 2 == 0:
        N = N >> 1
        p += 1
 
    if p == 0:
        return False
 
    q = 2**(p + 1) - 1
 
    if N != q:
        return False
 
    if isprime(N):
        return True
    else:
        return False

这里有些例子：

IsPerfect(137438691328)
True

IsPerfect(33550336)
True

## Note 11 is not Mersenne
2**(11 - 1) * (2**11 - 1)
2096128

IsPerfect(2096128)
False

IsPerfect(2658455991569831744654692615953842176) ## instant on my laptop
True

以下是所有小于 100 的素数：

mersenne = [2, 3, 5, 7, 13, 17, 19, 31, 61, 89]
not_mersenne = [11, 23, 29, 37, 41, 43, 47, 53, 59, 67, 71, 73, 79, 83, 97]

[IsPerfect(2**(p - 1) * (2**p - 1)) for p in mersenne]
[True, True, True, True, True, True, True, True, True, True]

[IsPerfect(2**(p - 1) * (2**p - 1)) for p in not_mersenne]
[False, False, False, False, False, False, False, False, False, False, False, False, False, False, False]