寻找第10001个素数_编程黑洞网

我正在解决Project Euler问题7，它说：

通过列出前六个素数：2、3、5、7、11和13，我们可以看到第六个质数是13。什么是10001质数？

这是我编写的代码：

def primes(n):
    primes = []
    attempt = 3
    while len(primes) < (n-1):
        for i in range(len(primes)):
            if attempt % primes[i] == 0:
                attempt += 2
                break
        else:
            primes.append(attempt)
            print (primes)
    return (primes)

测试一个数字，如果发现该数字可被列表中的质数之一整除，则for循环会中断，并从一个较大的数字开始。如果不能整除，则将其添加到素数列表中。这一直持续到列表达到所需的大小为止（在这种情况下为10000，而我省略了2，所以列表的最后一个成员是第10001个素数）。

问题是，这非常极端慢。我看过其他解决方案，显然可以在几秒钟内解决这个问题，即使不是更少。有什么方法可以使运行速度更快？

欢迎使用代码审查！最近有一个关于在此处查找素数总和的问题，即使目的不同，这也可能会有所帮助。

每当您在Project Euler上解决问题时，您都可以访问显示该问题的官方解决方案的文档，请查看发现问题的主页。

您可能会尝试是否尝试使用％primes [i]而不是将其与0进行比较。我想知道求反是否比与0进行比较是否更快，或者是否为平局？

#1 楼

首先，不要打印每个循环。这很浪费而且令人惊讶。另外，您不需要返回所有素数，您的摘要仅需要一个。您应该更清楚该功能的作用。返回最后找到的质数，可能还将您的函数重命名为prime。请不要忽略2，这只是一个奇怪而令人困惑的工作，您甚至没有在代码中进行解释。只需将其包括在素数的初始化中即可。

primes = [2]

也不需要执行

for i in range(len(primes)):
    if attempt % primes[i] == 0:

Python的for var in iterable语法更简单您可以直接获取值，这样更有效。它使用短路，并且在发现任何具有无效因数的值时将立即停止循环迭代。这比发现质数时中断要快，因为质数比非质数稀有得多，尤其是当您进入较高的值时。发现素数时增加尝试次数。这意味着每次您找到质数时，都必须以非常昂贵的方式再次对其进行检查，因为只有列表中的最后一个元素才会使质数失效。

\ $ \ begingroup \ $
谢谢！这些都是我一直在寻找的技巧（尽管我也很高兴看到数学上更有效的答案）印刷只是为了帮助自己进行故障排除，我无意中将其张贴在了这里。回复：全胜与全败，到底有什么区别？我以为我的for循环旨在将“尝试”除以质数（在列表中）并在任何时候尝试％primes [i] == 0时中断。是否由于编码方式而更快？
\ $ \ endgroup \ $
–尼古拉斯·哈桑（Nicholas Hassan）
2015年9月1日于19:44

\ $ \ begingroup \ $
@NicholasHassan我的理解是，内置函数几乎总是比Python中的for循环好，因为您可以将工作转移到更快的语言中，而不再使用Python。
\ $ \ endgroup \ $
–晴天
2015年9月1日于20:51

\ $ \ begingroup \ $
@NicholasHassan抱歉，迟到了，但是@sunny是正确的。这个答案证实了诸如sum之类的函数，任何和所有函数实际上都在C中运行（更快）而不是Python。
\ $ \ endgroup \ $
–SuperBiasedMan
2015年9月11日9:15在

\ $ \ begingroup \ $
但是，如果您想学习编程，请尝试避免所有这些技巧。您需要正确测试边缘情况，在这种情况下，必须了解nativefor循环。
\ $ \ endgroup \ $
– CodeYogi
2015年9月20日下午16:34

#2 楼

有时，当您的代码非常慢时，您只需要一种新算法即可。 SuperBiasedMan的解决方案对您的代码进行了许多出色的改进（将我的包装盒中的12.4s删除了不必要的print s后，仅为5.4s）。但是我们可以做得更好。问题是，我们仍在连续检查每个奇数，并且基本上从以前的所有工作中学到什么。 Eratosthenes的Sieve是用于计算大量素数的非常快速的算法。这个想法很简单：我们首先将所有数字作为主要候选者，然后遍历它们。如果发现仍然标记为质数的数字，则将其所有倍数标记为非质数。重复直到完成。

唯一的问题是我们需要将事物存储在内存中。对于10,000个素数来说，还算不错。素数的估计是众所周知的：p_n ~ n log(n)。这是一个非常好的估计，它的比率非常接近1，因此我们可以从两倍的内存开始进行良好测量：

def primes_sieve(n):
    p_n = int(2 * n * math.log(n))       # over-estimate p_n
    sieve = [True] * p_n                 # everything is prime to start
    count = 0

然后我们从2开始，然后开始舍去数字

    for i in range(2, p_n):
        if sieve[i]:                       # still prime?
            count += 1                     # count it!
            if count == n:                 # done!
                return i
            for j in range(2*i, p_n, i):   # cross off all multiples of i
                sieve[j] = False

就是这样。这需要0.1秒。原因是我们正在利用过去的工作。例如，一旦知道11是素数-我们就不必为121或407或其他任何东西做更多的工作。他们已经被淘汰了！

时间差随着我们计数的增加而增大。对于第100,001个素数，使用筛子可在0.8秒内给出答案，而幼稚的循环只需不到9分钟（8：53.5）。

#3 楼

整数除法（包括%模数指令）是一项相当昂贵的运算，比任何其他算术运算都要慢几倍，您必须执行许多运算。如果您能采用一种类似于筛子的方法，那将是很好的方法，其中模运算被逐步迭代代替。去寻找第10001个素数因此，我们需要一个类似于筛子的程序，该程序使我们能够扩展现有的素数列表。如果您熟悉Erathostenes的筛网，那么下面的代码应该不会太难理解：

def extend_primes(n, prime_list):
    if not prime_list:
        prime_list.append(2)
    first_in_sieve = prime_list[-1] + 1
    sieve = [True] * (n - first_in_sieve + 1)

    # Sieve all multiples of the known primes
    for prime in prime_list:
        start = prime * prime
        if start < first_in_sieve:
            # Rounded up integer division * prime
            start = ((first_in_sieve - 1) // prime + 1) * prime
        if start > n:
            break
        start -= first_in_sieve
        for idx in range(start, len(sieve), prime):
            print idx + first_in_sieve
            sieve[idx] = False

    # Sieve all multiples of the primes in the sieve
    for prime, is_prime in enumerate(sieve):
        if not is_prime:
            continue
        prime += first_in_sieve
        start = prime * prime
        if start > n:
            break
        start -= first_in_sieve
        for idx in range(start, len(sieve), prime):
            print idx + first_in_sieve
            sieve[idx] = False

    # Extend prime_lsit with new primes
    prime_list.extend(p + first_in_sieve
                      for p, is_p in enumerate(sieve) if is_p)

现在，您可以扩展素数列表了，您只需要扩展它，直到其中有足够的项目。一种不太复杂的解决方法可能是：

def find_nth_prime(n):
    prime_list = [2]
    limit = n
    while len(prime_list) < n:
        extend_primes(limit, prime_list)
        limit *= 2
    return prime_list[n - 1]

这会在不到一秒钟的时间内产生正确的结果。，您可以利用素数计数函数从上方受对数积分限制的事实，并进行常规筛分直至达到该值。但这会使该问题失去一些算法上的乐趣。

#4 楼

您的脚本运行缓慢的原因之一是您正在构建一个数组：

primes.append(attempt)

随着时间的流逝，该数组将变得很大，并且性能下降。由于您要查找的答案是一个奇异值，所以为什么不优化对数组的需要：

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while (i * i <= n):
        if n % i == 0:
            return False
        i = i + 1
    return True

def n_prime(n):
    i = 2
    while n > 0:
        if is_prime(i):
            n = n - 1
            if n == 0:
                return i
        i = i + 1
    return -1

    print n_prime(10001)

在例程中，通过检查实现is_prime(n)如果可以被它之前的质数整除。而我通过检查n是否可以被2..sqrt（n）中的整数整除来降低复杂度。即我也懒洋洋地检查非素数，但是，我仅通过检查最多sqrt（n）来优化了搜索。

然后我们循环循环调用is_prime(i)直到我们已经遇到n个素数。

对于您的特定问题，答案是104743。

\ $ \ begingroup \ $
当您谈论列表创建时，我认为您将要谈论迭代器及其带来的所有好处。不幸的是，您没有这样做，所以我认为您很想知道如何通过使用迭代器来改进代码。您在这里：gist.github.com/SylvainDe/a29d616684b45f28bd3c。我保留了中间版本，以便您可以了解情况如何变化。最终，您具有is_prime（3行，可能是2行），nth（2行），yield_primes（3行），您可以轻松地编写它们。
\ $ \ endgroup \ $
– SylvainD
2015年9月2日15:45在

#5 楼

您的代码中有一个有趣的优化：您使用第一个质数为2的事实跳过此值的所有测试，并将每个测试加2。

在注释中调用此事实！

我同意SuperBiasedMan的说法，它可能会造成混淆，应予以警告。一个令人困惑的地方是while循环比较，您必须编写< (n - 1)。当实际数字在比较中时，通常比较容易阅读比较，无论是从小于等于更改为等于还是小于等于，或者如本例中那样更改初始化。通过用primes = [2]初始化它来将值添加到列表中，或者，如果您想让它变得冗长，请将该值添加到列表中：
测试2，这是对性能的影响，您可以通过将其递增2来解决。要么在第二次迭代中开始循环，要么不将其添加到列表中。

尤其是在这样的数学问题中，因此始终需要在速度和可读性之间进行权衡。将其与您的代码用户隔离开，仅在实际必要时进行优化，但要做出明智的决定。通常，业务逻辑是最清晰的，而类似这样的后端算法是最快的。研究！），或者您可以优化自己的产品。对于初学者，您不需要检查整个列表-直到被测试的因子大于或等于您当前潜在主要候选人的平方根。 13不会是14的因数，您最多只需要检查3。但是它更快吗？平方根在某些硬件上很昂贵。也许使用平方根近似。您需要基准测试。现在，为什么您的主要验证中有平方根？需要评论！

\ $ \ begingroup \ $
您无需评论所有内容。我不得不说平方根检查是进行素数检查时的常识，如果由于某种原因而决定不使用注释，则注释很可能很重要，因为下一个人可能会把它尝试加快速度。
\ $ \ endgroup \ $
–user34073
2015年9月1日于20:26