如何让这段Python代码运行更快？[欧拉计划第7题]

Question

我正在尝试完成这个Project Euler挑战：

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

第10001个质数是多少？

我的代码似乎是正确的，因为它对小数字有效，例如第6个质数是13。

如何改进代码，使其在处理较大数字（例如10001）时运行更快？

以下是代码：

#Checks if a number is a prime
def is_prime(n):
    count = 0
    for i in range(2, n):
        if n%i == 0:
            return False
            break
        else:
            count += 1
    if count == n-2:
        return True

#Finds the value for the given nth term     
def term(n):
    x = 0
    count = 0
    while count != n:
        x += 1
        if is_prime(x) == True:
            count += 1
    print x


term(10001)

更新:

感谢您的回复。我应该更清楚地表达，我不是想加快解释器的速度或找到一个更快的解释器，因为我知道我的代码并不好，所以我在寻找使我的代码更高效的方法。

- Adnan

---

解题欧拉计划的诀窍在于找到正确的算法。如果你的解决方案运行得太慢，那么你使用的就是错误的算法；对性能进行"微调"（让代码运行更快）是没有帮助的。 - bstpierre

这个链接可以帮助你检查：http://codereview.stackexchange.com/questions/44929/prime-number-util-class - JavaDeveloper

一个类似的线程[https://codereview.stackexchange.com/questions/188053/project-euler-problem-7-in-python-10001st-prime-number][1]。我的方法是：生成和枚举。 - Matt Cao

Answer 1

思考一下以下几个问题：

• 你真的需要检查除数直到n-1吗？你可以提前停止吗？
• 除了2以外，你真的需要检查所有2的倍数的除法吗？
• 那么多个3的倍数呢？5的倍数呢？有没有一种方法将这个想法扩展到之前测试过的所有质数的所有倍数上？

- Jerome

---

+1 有用的提示，尽管我怀疑许多人（包括 OP）自己无法想出这个算法的实现方式...不过，执行前两个步骤可能已经足够解决这个问题了。 - user395760

让他自己解决问题——纠正他的思维而不是答案。 - agf

不要发这样的答案，让别人自己慢慢领悟，体验那个“顿悟”的时刻。这会破坏掉一切。 - Abhinav Gauniyal

Answer 2

Project Euler的目的并不是为了学习编程，而是为了思考算法。在问题＃10上，您的算法需要比问题＃7更快，因此您需要想出一种更好的方法来查找质数，而不是想出一种更快运行Python代码的方法。人们通过思考数学，在时间限制内用比您现在使用的计算机慢得多的速度解决这些问题。

顺便说一下，如果您确实需要帮助思考这个问题，请在https://math.stackexchange.com/上询问有关质数算法的问题。

- agf

Answer 3

一个更快的解释器并不能解决问题。即使是使用C或汇编语言编写的实现也不够快（无法在欧拉计划中的“约一秒”时间范围内）。坦率地说，你的算法很差。通过研究和思考，您可以编写一个运行速度比当前使用本地代码实现的算法更快的算法（我不会具体说明，部分原因是这是您的工作，部分原因是我无法立即确定需要进行多少优化）。

- user395760

Answer 4

许多欧拉问题（包括这个）都设计成可以在几乎任何硬件和编译器上以可接受的时间计算出解决方案（嗯，也许不包括PDP-11上的INTERCAL）。

您的算法是有效的，但它具有二次复杂性。使用更快的解释器将为您提供线性性能提升，但二次复杂性将在计算10,000个质数之前远远超过它。有更低复杂度的算法，请找到它们（或谷歌它们，在此没有羞耻感，而且您仍然会学到很多），并实现它们。

- tdammers

Answer 5

检查质数时，您不必运行到n-1或n/2....

为了更快地运行它，您只需检查到n的平方根即可。

这是我知道的最快算法。

def isprime(number):
        if number<=1:
            return False
        if number==2:
            return True
        if number%2==0:
            return False
        for i in range(3,int(sqrt(number))+1):
            if number%i==0:
                return False
        return True

- m0rpheu5

Answer 6

不讨论算法的情况下，PyPy 解释器在像这样紧密的数字计算方面可能比普通的 CPython 解释器快得多。你可以尝试一下。

- Jeremy

Answer 7

另一种快速的Python解决方案：

import math
prime_number = 4 # Because 2 and 3 are already prime numbers
k = 3 # It is the 3rd try after 2 and 3 prime numbers
milestone = 10001
while k <= milestone:
    divisible = 0
    for i in range(2, int(math.sqrt(prime_number)) + 1):
        remainder = prime_number % i
        if remainder == 0: #Check if the number is evenly divisible (not prime) by i
            divisible += 1
    if divisible == 0:
        k += 1
    prime_number += 1
print(prime_number-1)

- Irmak Aydeniz

Answer 8

我采用了不同的方法。我们知道所有2的倍数都不会是质数（除了2），我们也知道所有非质数可以分解为质因数。

例如：

12 = 3 x 4 = 3 x 2 x 2

30 = 5 x 6 = 5 x 3 x 2

因此，我遍历了一个奇数列表，累积了一个质数列表，并仅尝试在此列表中找到与奇数的模数相匹配的质数。

#First I create a helper method to determine if it's a prime that 
#iterates through the list of primes I already have
def is_prime(number, list):
    for prime in list:
        if number % prime == 0:
            return False
    return True

编辑：最初我是用递归的方式写的，但我认为迭代的情况更简单。

def find_10001st_iteratively():
    number_of_primes = 0
    current_number = 3
    list_of_primes = [2]
    while number_of_primes <= 10001:
        if is_prime(current_number, list_of_primes):
            list_of_primes.append(current_number)
            number_of_primes += 1
        current_number += 2
    return current_number

- Victor

Answer 9

import time
t=time.time()
def n_th_prime(n):

    b=[]
    b.append(2)
    while len(b)<n :
        for num in range(3,n*11,2):
            if all(num%i!=0 for i in range(2,int((num)**0.5)+1)):
                b.append(num)


    print list(sorted(b))[n-1]
n_th_prime(10001)
print time.time()-t

打印

104743

0.569000005722 秒

- Ahmad

Answer 10

Pythonic的答案

import time
t=time.time()
def prime_bellow(n):
   b=[]
   num=2
   j=0
   b.append(2)
   while len(b)-1<n:
        if all(num%i!=0 for i in range(2,int((num)**0.5)+1)):
            b.append(num)
        num += 1
   print b[n]
 prime_bellow(10001)
 print time.time()-t

打印

104743

   0.702000141144 second

- Ahmad