如何让这段Python代码运行得更快？[Project Euler 问题 #7]

Question

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

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

那么第10,001个质数是什么呢？

我的代码看起来是对的，因为它在处理小数字时能正常工作，比如第六个质数是13。

我该如何改进代码，让它在处理更大的数字，比如10,001时运行得更快呢？

代码如下：

#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)

更新：

谢谢大家的回复。我应该更清楚地说明，我并不是想加快解释器的速度或者寻找一个更快的解释器，因为我知道我的代码并不完美，所以我在寻找让我的代码更高效的方法。

Answer 1

光是一个更快的解释器是没用的。即使是用C语言或汇编语言写的实现，也无法达到项目Euler要求的“差不多一秒”的速度。说得直白点，你的算法实在太差了。多做一些研究和思考，会帮助你写出一个在慢得像狗一样的解释器中运行得比你现在用本地代码实现的算法还要快的算法（我不想具体说哪种算法，部分原因是这得你自己去找，部分原因是我也不知道需要多少优化）。

Answer 2

Project Euler的目的是让你思考算法，而不是单纯学习编程。在第10题中，你的算法需要比第7题更快等等。所以，你需要想出一种更好的方法来找质数，而不是仅仅提高Python代码的运行速度。其实，有些人用比你现在用的电脑慢得多的设备，在时间限制内解决这些问题，关键在于他们思考了数学。

如果你真的需要帮助思考质数算法，或许可以去https://math.stackexchange.com/问问。

Answer 3

这里有几个问题可以思考：

• 你真的需要检查到 n-1 吗？你能更早地停止检查吗？
• 除了 2 以外，你真的需要检查所有 2 的倍数吗？
• 那 3、5 的倍数呢？有没有办法把这个想法扩展到之前检查过的所有质数的倍数上？