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 不被认为是“素数”数字，即使它是，而且我知道如果它除以范围内的任何东西，它自动不是素数，因此 return False 语句。但我的问题是 平方根“n”在这里扮演什么角色？

ps 本人很新手，一个月前才接触编程。

原文由 Giancarlo Manuel Guerra Salvá 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在 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 ）那么我们可以每 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() 截断该值）

考虑下一个奇数（因为除 2 以外的所有偶数都不是质数）5005，同样的输出：

  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： 素数测试 是计算机科学中一个有趣的问题。

原文由 dawg 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

对于 n**.5 ，您不是对 n 进行平方，而是取平方根。

考虑数字 20；整数因子是 1、2、4、5、10 和 20。当你用 20 除以 2 得到 10 时，你知道它也可以被 10 整除，而无需检查。当您将它除以 4 得到 5 时，您知道它可以同时被 4 和 5 整除，而无需检查 5。

在达到因素的这个中间点后，您将没有更多的数字来检查您之前尚未识别为因素的数字。因此，你只需要走一半就可以知道某个东西是不是质数，而这个中途点可以通过对数求平方根来找到。

此外，1 不是素数的原因是因为素数被定义为具有 2 个因子，即 1 和它本身。即2为1*2，3为1*3，5为1*5。但是 1 (1*1) 只有 1 个因子，它本身。因此，它不符合这个定义。

原文由 cpuguy89 发布，翻译遵循 CC BY-SA 3.0 许可协议