问题描述

在Internet上进行的许多质数测试中，请考虑以下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，因此我们消除了n：

1. 不是2或3（素数），
2. 甚至没有（用n%2）和
3. 不能被3整除（用n%3），那么我们可以每6th 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的下一个奇数（因为除2以外的所有偶数都不是质数），所以输出相同的东西：

 5
False

极限是平方根，因为x*y == y*x该函数仅需经过1次循环即可发现5005被5整除，因此不是素数。由于5 X 1001 == 1001 X 5（并且两者均为5005），因此我们不需要一直循环到1001来知道在5时知道什么！

现在，让我们看一下您拥有的算法：

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整除，因此我们仅通过测试大于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：素数测试是计算机科学中一个有趣的问题。

解决方法

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

    return True