Python语言的isPrime函数

Question

我在网上找了一些资料，终于解决了这个问题，结果是这样的：

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

不过我真正想问的是，怎么做这个，为什么要这样做。我知道1不被认为是“质数”，尽管它其实是，而且我明白如果它能被范围内的任何数整除，那它就自动不是质数，所以返回False的语句也是这样。但我想问的是平方根在这里有什么作用？

顺便说一下，我刚接触编程一个月，经验还很少。

Answer 1

这个问题之前有人问过，但我有一个更简单的解决办法给你。

def isNotPrime(Number):
    return 2 not in [Number,2**Number%Number]

这个数学运算大多数情况下会返回2，如果这个数字是质数的话，而不是返回2。但是如果给定的数字是2，它会被添加到我们正在查看的列表中。

举个例子：

2^5=32    32%5=2
2^7=128   128%7=2
2^11=2048 2048%11=2

反例：

2^341%341=2,  but 341==11*31
2^561%561=2,  but 561==3*11*17
2^645%645=2,  but 645==3*5*43

不过，isNotPrime() 函数如果数字不是质数的话，会可靠地返回 True。

Answer 2

用 n**.5 这个写法，你不是在把 n 平方，而是在求 n 的平方根。

比如说数字 20，它的整数因子有 1、2、4、5、10 和 20。当你用 20 除以 2 得到 10 时，你就知道 20 也能被 10 整除，这个你不用再去验证。再比如，你用 20 除以 4 得到 5，这样你也知道 20 能被 4 和 5 整除，这个也不用再去检查 5。

当你找到一半的因子后，就没有其他的数字需要检查了，因为你之前已经找到了所有的因子。因此，要判断一个数是不是质数，只需要检查到它的平方根就可以了。

另外，1 不是质数的原因是，质数的定义是有两个因子，分别是 1 和它自己。比如 2 是 1*2，3 是 1*3，5 是 1*5。但 1（1*1）只有一个因子，就是它自己。所以它不符合这个定义。

Answer 3

在网上有很多关于质数的测试方法，这里我们来看一个用Python写的函数：

def is_prime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int(n**0.5)
  # since all primes > 3 are of the form 6n ± 1
  # start with f=5 (which is prime)
  # and test f, f+2 for being prime
  # then loop by 6. 
  f = 5
  while f <= r:
    print('\t',f)
    if n % f == 0: return False
    if n % (f+2) == 0: return False
    f += 6
  return True    

因为所有大于3的质数都是6n ± 1的形式，所以我们可以排除以下情况：

1. n 不能是2或3（这两个是质数），
2. n 不能是偶数（用 n%2 来判断），
3. n 不能被3整除（用 n%3 来判断），这样我们就可以测试每隔6个数的 n ± 1。

比如质数5003：

print is_prime(5003)

输出结果：

 5
 11
 17
 23
 29
 35
 41
 47
 53
 59
 65
True

这一行 r = int(n**0.5) 计算出70（因为5003的平方根是70.7318881411，int() 会把这个值取整）。

接下来考虑下一个奇数5005，输出结果也是一样：

 5
False

这里的限制是平方根，因为 x*y == y*x，所以这个函数只需要循环一次就能发现5005能被5整除，因此它不是质数。因为 5 X 1001 == 1001 X 5（这两个都是5005），所以我们不需要在循环中一直到1001才能知道5005的情况！

---

现在，让我们看看你有的算法：

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

    return True

这里有两个问题：

1. 它没有检查 n 是否小于2，而小于2的数没有质数；
2. 它测试了从2到 n**0.5 之间的所有数字，包括所有的偶数和奇数。因为大于2的偶数都不是质数，所以我们可以通过只测试大于2的奇数来加快速度。

所以：

def isPrime2(n):
    if n==2 or n==3: return True
    if n%2==0 or n<2: return False
    for i in range(3, int(n**0.5)+1, 2):   # only odd numbers
        if n%i==0:
            return False    

    return True

好的，这样可以加快大约30%的速度（我测试过...）

我用的算法 is_prime 速度快了大约2倍，因为它只循环每隔6个整数。（我再次测试过。）

---

附注： x**0.5 是平方根：

>>> import math
>>> math.sqrt(100)==100**0.5
True

---

附注2： 质数测试 是计算机科学中的一个有趣问题。