codeforces timelimit (230B T-素数) python3.6

Question

我的代码有一个问题，我使用eratosthenes这个函数来创建一个列表，我只是做了一个很大的内存大小列表(1000000)，主要是我输入了codeforce input()并让它们sqrt()，所以，我不知道为什么我的代码timelimit超过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")

当我引用别人的代码时，我认为我的代码的运行时间类似于其他人的代码，或者我错了。

Answer 1

我认为你的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，看看它是否更好。