查找10001st质数(在python中)? [英] Finding the 10001st prime number (in python)?

问题描述

我目前正在尝试使用erasthonese筛子的实现，但是要找到很长的质数列表仍需要花费很长时间.

I'm currently trying to use an implementation of the sieve of erasthonese, but it still takes a very long time to find a long list of prime numbers.

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]

我试图硬编码筛子应达到的值，并且希望它足够长，这样我才能找到10002nd元素.目前，运行时是一个大问题，因此，希望获得有关减少运行时的任何提示或建议或其他任何方式.

I tried to hard code to what value the sieve should run to, and hopefully, it's long enough so that I can find the 10002nd element. Runtime is a big problem at the moment, so any tips or advice on cutting runtime down or anything else is appreciated.

推荐答案

如果您特别希望改进此代码，那么您可以做的第一件事就是使用set存储非素数.

If you are interested in improving this code in particular, then the first thing you could do is use a set to store the non primes.

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

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

This prevents repetition of numbers within the list, and makes searches within the list fast. This will vastly improve your run time.

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的质数了:

Now finding the 10,001 prime is achievable:

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

这篇关于查找10001st质数(在python中)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！