在Python中找到第10001个素数？

Question

我目前正在尝试使用erasshonese的一个实现，但是仍然需要很长时间才能找到一个很长的素数列表。在

def sieve(n=1000000):
    not_prime = []
    prime = []
    for i in range(2, n+1): 
        if i not in not_prime:
            prime.append(i) 
            for j in range(i*i, n+1, i): 
                not_prime.append(j) 
    return prime[10002]

我试图硬编码到筛子应该运行到什么值，希望它足够长，这样我就能找到10002元素。运行时是目前的一个大问题，所以任何关于减少运行时的提示或建议都是值得赞赏的。在

Answer 1

如果您对改进这段代码特别感兴趣，那么您可以做的第一件事就是使用set来存储非素数。在

def sieve_set(n=1000000):
    not_prime = set()
    primes = []
    for i in range(2, n+1): 
        if i not in not_prime:
            primes.append(i) 
            for j in range(i*i, n+1, i): 
                not_prime.add(j)

    return primes

这可以防止在列表中重复数字，并使搜索在列表中快速进行。这将大大改善您的运行时间。在

^{pr2}$

现在找到10001素数是可以实现的：

In [3]: %timeit sieve_set(105000)
10 loops, best of 3: 26.6 ms per loop

In [4]: sieve_set(105000)[10000]
Out[4]: 104743