时间戳

首页 > 解决方案 > 几乎完美的卡蒂斯（超过时间限制）

python - 几乎完美的卡蒂斯（超过时间限制）

问题描述

希望你能帮助我解决这个问题：

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

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

这是我的代码。第一个测试通过但第二个没有它给我的消息（超过时间限制）

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;

错误在哪里？或者我该如何优化它？先感谢您

标签： python

解决方案

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

请注意，如果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您将打印两次消息时，可以通过删除printbefore轻松解决break。

推荐阅读