找到第 10001 个质数（在 python 中）？

Question

我目前正在尝试使用 erasthonese 筛法的实现，但仍然需要很长时间才能找到一长串素数。

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

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

In [1]: %timeit -n 1 -r 1 sieve(10000)
1 loops, best of 1: 775 ms per loop

In [2]: %timeit -n 1 -r 1 sieve_set(10000)
1 loops, best of 1: 5.85 ms per loop

现在可以找到 10,001 个素数了：

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

找到第 10001 个质数（在 python 中）？

Finding the 10001st prime number (in python)?

python

optimization

primes

mathematical-optimization

sieve-of-eratosthenes