近乎完美的Kattis（超过时间限制）

Question

希望您能在这个问题上帮助我：

所以这个问题在Kattis中几乎是完美的

https://open.kattis.com/problems/almostperfect

这是我的密码。第一个测试通过，但第二个测试不通过，它会给我am消息（超过时间限制）

def isperfect(n):

l=0
for i in range(1,n):
    if n%i==0:
        l+=i
    if l>n+2 :
        print(f"{n} not perfect")
        break
    
if(l==n):
    print(f"{n} perfect")
elif abs((n-l))<=2:
    print(f"{n} almost perfect")
else :
    print(f"{n} not perfect")
    

while True:


try :
    n = int(input())
    isperfect(n)
except EOFError:
    break;

错在哪里？或者我如何优化它？ 先谢谢你

Answer 1

问题是代码太慢了。幸运的是，有一个简单的优化，可以节省你

注意，如果d是n的除数，那么n / d也是一个除数。此外，如果d小于sqrt(n)，则n / d大于sqrt(n)（反之亦然）

这实际上意味着我们只需要检查到sqrt(n)的数字，而不是检查到n的所有数字。对于我们找到的每一个除数d，我们也确保将n / d添加到除数和中，除非d是1或者正好是sqrt(n)

下面是代码中可能出现的情况：

    l = 1
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            l += i
            if i < sqrt(n): l += n // i
        if l > n + 2: break

另一个小错误是，当l > n + 2时，您将打印两次消息，这很容易通过删除break之前的print来解决

Answer 2

import sys
import math
def almostPerfect(num):

    count = 1
    for i in range (2,int(math.sqrt(num)) + 1):
        if(num % i == 0):
            count += i
            if(i*i != num):
                count += num // i

    if(count == num):
        return "{} perfect".format(num)
    elif (count == (num-2)):
        return "{} almost perfect".format(num)
    elif (count == (num+2)):
        return "{} almost perfect".format(num)
    elif (count == (num-1)):
        return "{} almost perfect".format(num)
    elif (count == (num+1)):
        return "{} almost perfect".format(num)
    else:
        return "{} not perfect".format(num)

for line in sys.stdin.readlines():
    line = int(line)
    print(almostPerfect(line))

这可能是另一个适用于python的解决方案，我认为我们需要注意(i*i != num)，这样我们就不会开始添加相同的数字。祝您今天过得愉快！！😊😊