0

我的代码有问题，我使用eratosthenes这个函数来创建一个列表，我只是制作了一个大内存大小列表（1000000），主要我输入codeforces input（）并让它们sqrt（），所以，我不知道为什么我的代码时间限制超过2000ms，请帮我解决这个问题。

import math

def eratosthenes(n):  # creative the prime list
    IsPrime = [True] * (n + 1)
    IsPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if IsPrime[i]:
            for j in range(i * i, n + 1, i):
                IsPrime[j] = False
    return [x for x in range(2, n + 1) if IsPrime[x]]

#  main code
input()
li = list(map(int, input().split()))
nl = eratosthenes(1000000)
for i in li:
    i = math.sqrt(i)
    if int(i) == i:
        print("YES" if i in nl else "NO")
    else:
        print("NO")

当我引用它们时，我认为我的代码的运行时间与其他代码相似，否则我错了。

4

1 回答 1

0

我认为您的eratosthenes功能还可以，主要瓶颈是您在回答问题时...

print("YES" if i in nl else "NO")

在这部分中，您在 nl 列表中搜索，这是 O(p)，其中 p 是 nl 中素数的数量。小于 N 的素数的数量是 O(N/logN)，特别是这里大约 78500 个数字。

因此，如果输入包含一些大正方形，但不是 T 素数，您的代码将执行大约 10^5 * 78500 ~= 8*10^9 操作，这会产生 TimeLimitError。

您可以使用 IsPrime 数组来检查数字是否为素数。

除了这个加快速度，我不知道python sqrt有多快，但是你可以用二进制搜索计算sqrt，看看它是否更好。

于 2021-11-21T07:55:32.887 回答