python - 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 语句。但我的问题是平方根“n”在这里扮演什么角色？

附:我非常缺乏经验，一个月前才被介绍编程。

Answer 1

在互联网上流传的许多素数测试中，请考虑以下 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    

Since all primes > 3是 6n ± 1 的形式，一旦我们消除 n 是:

1. 不是 2 或 3(它们是素数)和
2. 甚至(使用 n%2)和
3. 不能被 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 的下一个奇数(因为除了 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:primality testing是计算机科学中一个有趣的问题。