如何在Python中检查一个数字是否为素数

这个教程将教你如何编写一个Python程序来检查一个数字是质数还是非质数。

如果你曾经参加编码测试，你肯定会遇到一个数学问题，即质数测试或检查一个数字是否为质数的问题。在接下来的几分钟内，你将学会如何提出这个问题的最优解。

在本教程中，你将：

回顾质数的基本知识,
编写Python代码来检查一个数字是否为质数，并且
进一步优化它，得到一个O(√n)的运行时间算法。

为了实现这一切以及更多内容，请开始吧。

什么是质数？

让我们从回顾质数的基本知识开始。

在数论中，自然数n被称为prime，如果它有正好两个因子：1和这个数本身(n)。从你在学校学的数学中回忆一下：如果一个数i可以整除另一个数n，那么这个数就是数n的因子。✅

下表列出了一些数字，以及它们的所有因子和它们是否是质数。

n	因子	是否是质数？
1	1	否
2	1, 2	是
3	1, 3	是
4	1, 2, 4	否
7	1, 7	是
15	1, 3, 5, 15	否

从上表中，我们可以得出以下结论：

2是最小的质数。
1是任何数的因子。
每个数n都是它自己的因子。

所以1和n都是任何数n的平凡因子。质数除了这两个因子之外，不应该有其他因子。

这意味着当你从2到n-1遍历时，你不应该能够找到一个非平凡因子，它能够整除n并且没有余数。

用Python检查一个数字是否为质数的O(n)算法

在本节中，让我们把上面的方法正式化为一个Python函数。

你可以使用Python中的range()对象循环遍历从2到n-1的所有数。

在Python中，range(start, stop, step)返回一个range对象。你可以迭代遍历这个range对象，以获取从start到stop-1的步长为step的序列。

由于我们需要从2到n-1的整数集合，我们可以指定range(2, n)并将其与for循环结合使用。

下面是我们想要做的：

如果你找到一个能够整除n而没有余数的数字，你可以立即得出结论，该数字不是质数。

如果你在从2到n-1的所有数字范围内循环遍历而没有找到能够整除n的数字，那么该数字是质数。

检查质数的Python函数

使用上述方法，我们可以定义如下的函数is_prime()。

def is_prime(n):
  for i in range(2,n):
    if (n%i) == 0:
      return False
  return True

现在让我们解析上述函数定义。

上述函数is_prime()接受一个正整数n作为参数。
如果你在指定的范围(2, n-1)内找到一个因子，该函数返回False，因为该数字不是质数。
如果你遍历整个循环而没有找到一个因子，它将返回True。

接下来，让我们调用该函数并验证输出是否正确。

在上面的输出中，您可以看到2和11是素数（函数返回True）。而8和9不是素数（函数返回False）。

如何优化Python函数is_prime（）
我们可以在这里进行一点优化。观察下面的因子列表。

数字因子
6 1, 2, 3, 6
10 1, 2, 5, 10
18 1, 2, 3, 6, 9, 18

我们可以看到，大于n / 2的n的唯一因子是n本身。

因此，这意味着您不必循环到n-1。您可以仅运行循环到n / 2。

如果在n / 2之前找不到非平凡因子，那么在n / 2之后也找不到。

现在让我们修改函数is_prime（）以在范围（2，n / 2）内检查因子

def is_prime（n）：
for i in range（2，int（n / 2））：
if（n％i）== 0：
return False
return True

让我们继续通过几个函数调用验证输出。

is_prime（9）
# False

is_prime（11）
# True

即使看起来我们已经进行了优化，但从运行时间复杂性的角度来看，此算法也不比以前的算法更有效。实际上，它们都具有O（n）的运行时间复杂性：与n的值成比例或与n成线性比。

我们能做得更好吗？我们可以！

以O（√n）算法检查Python中的素数
碰巧一个数字的因子是成对出现的。

如果a是数字n的因子，则存在一个因子b，使得a x b = n，或者简单地说，ab = n。

让我们通过一个例子来验证这一点。

下表显示了数字18的成对因子。如果您愿意，您可以验证几个更多数字的因子。

还要注意，√18约为4.24。

在成对出现的因子（a，b）中，您可以看到如果a小于4.24，则b大于4.24-在此例子中为（2，18）和（3，6）。

数字18的因子在数轴上绘制如下。

如果数字n恰好是一个完全平方数，您将得到a = b = √n作为其中一个因子。

看看下表中36的因子。由于36是一个完全平方数，a = b = 6是其中一个因子。对于所有其他因子对（a，b），a 6成立。

总结一下，我们有以下内容：

每个数字n都可以写成n = a x b
如果n是一个完美的square，那么a = b = √n。
如果a < b，那么a < √n且b > √n。
否则，如果a > b，那么a > √n且b < √n。

所以，不必遍历所有小于n/2的整数，可以选择运行到√n。这比之前的方法更高效。

如何将is_prime()修改为O(√n)的算法

让我们继续优化Python中检查素数的函数。


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

现在，让我们解析上述函数定义：

要计算一个数的平方根，让我们导入Python的内置math模块，并使用math.sqrt()函数。
由于n可能不是一个完全平方数，我们需要将其转换为整数。使用int(var)将var转换为int。
为了确保我们实际上是检查到√n，我们在range()函数中添加一个加一，因为range()函数默认不包括范围的末端。

下面的代码单元格验证了我们的函数is_prime()的正确性。

is_prime(8)
# False

is_prime(15)
# False

is_prime(23)
# True

在下一节中，让我们创建一些简单的图表来直观地理解O(n)和O(√n)。

对比O(n)和O(√n)的可视化

▶️ 在Jupyter notebook环境中运行以下代码片段。

import numpy as np
import seaborn as sns
import pandas as pd


n = 20

x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)

上面的代码片段展示了如何绘制一系列值的n和√n的曲线。

我们使用NumPy的arange()函数创建一个数字数组。
然后，我们将n和√n的值收集到一个pandas DataFrame中，范围为20，但不包括20。
接下来，我们使用seaborn’s lineplot()函数绘图。

从下面的图中，我们可以看到√n明显小于n。

现在，让我们将范围增加到2000，并重复上述步骤。

import numpy as np
import seaborn as sns
import pandas as pd


n = 2000

x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)