为什么我的代码在编辑后不能运行得更快？

Question

我是计算机科学和程序设计的新手。我参加了一个免费的在线编码课程，其中一个作业是写一个程序，生成第1000个素数。你知道吗

仅供参考，这是Python2.5.4版本

以下是我从这个论坛的另一个帖子中复制（并编辑了一点）的原始代码：

def isprime(n):

    if n<2:
        return False
    else:
        for i in range(2,(n/2+1)):
            if n%i==0:
                return False
        else:
            return True

def nthprime(n):
    x=[]
    j=2
    while len(x)<n:
        if (isprime(j)) == True:
            x.append(j)
        j =j+1
    return(x[n-1])

print nthprime(1000)

但是，我认为我可以通过重写isprime（n）函数使程序更快，如下所示：

def isprime(n):# First the primality test
    i=1
    if n<2:
        return False
    if (n!=2 and (n/2*2==n)):
        return False
    if n==3:
        return True
    if n==5:
        return True
    else:
        while i <= (n/2+1):
            i+=2
            if n%i==0:
                return False
        else:
              return True  

这样，当它只检查n是否可以被奇数整除时（到代码中的这一点，我们已经知道n是奇数，因此不能被任何偶数整除）。你知道吗

我认为用这种方法重写它会使程序的运行速度提高一倍（因为它只检查一半的数字），但它所用的时间似乎与以前相同，甚至稍长。你知道吗

还有，有没有办法重写第二段代码来消除：

if n==3:
    return True
if n==5:
    return True 

唯一的原因，我包括这是因为我意识到我的算法是产生“假”为3和5，即使他们是素数。你知道吗

Answer 1

我知道你的优化是为了什么，但我认为你实现的逻辑不是你想要的。想想其他方法，你可以减少你必须检查的数字。你知道吗

我推荐的第一个方法是立即排除偶数：

def isprime(n):
    if n < 2 or n % 2 == 0:
        return False
    # ...

另一个你正在检查的比你需要的更多的地方是在优化失败时你所依赖的因素检查。你不需要一直到n / 2；你需要担心的最大的因素是sqrt(n)（一旦你通过了根n，你就开始检查那些你已经检查过的因素，例如，如果你正在检查n = 6，一旦你检查了2，你已经检查了3）。下面是相应的优化：

def isprime(n):
    # ...
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False

总之，这里是新的isprime（编辑：带评论提示）：

def isprime(n):
    if n == 2: return True
    if n % 2 == 0: return False

    for i in xrange(3, int(n ** 0.5) + 1, 2):
        if n % i == 0: return False

    return True

计算nthprime(5000)，这两个优化将我的时间从8.497秒缩短到0.108秒。你知道吗

编辑：demo