Sublime Text中“is_prime” Python函数的问题

Question

我正在尝试运行以下简单的代码：

import math
def is_prime(N):
    for i in range(2, int(math.sqrt(N))):
        if (N % i == 0) :
            print(str(N) + " is not prime")
            return False 
    print(str(N) + " is prime")
    return True

这个代码的目的是判断一个数字是否是质数（其实挺简单的）。不过，我就是让这个代码无法正常工作。我发现问题可能出在 int(math.sqrt(N)) 这行代码上，但我不明白为什么它不行，因为我运行 int(math.sqrt(134)) 的时候是没问题的。这个代码里有没有我看不出来的错误呢？

我还开始怀疑编译器是否有问题。我在使用Sublime Text 3，配合默认的Python构建工具。也许我在Sublime Text上做错了什么？

编辑：我忘了提到具体的问题。当我运行 is_prime(8) 的时候，它返回 8 is prime。但是没有显示任何错误。不过需要注意的是，运行 is_prime(134) 的时候，它确实如预期返回 134 is not prime。如果有人想的话，我可以尝试用 for 循环。

Answer 1

我对你程序中的一些代码进行了修改，让它运行得更高效一些。你的循环是从1到N的平方根都检查一遍。如果你先检查这个数字是否能被2整除，也就是判断它是不是偶数，那么就可以把所有偶数都排除掉，只检查奇数，比如3、5、7等等。

import math
def is_prime(N):
    if(N == 2):
        print(str(N) + " is a prime")
        return True
    if((N % 2 == 0)or(N == 1)):
        print(str(N) + " is not prime")
        return False
    for i in range(3,int(math.sqrt(N))+1,2):
        if(N % i == 0):
            print(str(N) + " is not prime")
            return False
    print(str(N) + " is prime")
    return True

Answer 2

试试这个：

import math
def is_prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n%i == 0 :
            return False 
    return True

range() 这个函数在到达第二个数字之前就停止了。所以在这种情况下，你想要测试那个数字，所以需要先向下取整，然后再加一。

---

更高效的版本（速度提升大约是 x10 - x1000）：

def memoise(func):
    memory = {}
    def wrapper(n):
        if n in memory:
            return memory[n]
        ret = func(n)
        memory[n] = ret
        return ret
    return wrapper

@memoise
def is_prime(n):
    if n <= 3:
        return n > 1
    if not n%2 or not n%3:
        return False

    for i in range(5, int(n**0.5)+1, 6):
        if not n%i or not n%(i+2):
            return False
    return True

---

在解释器中玩玩：

>>> math.sqrt(8)
2.8284271247461903
>>> int(math.sqrt(8)) + 1
3
>>> for i in range(2, 2):
        print(i)

>>> for i in range(2, 3):
        print(i)

2