素数的定义-素数的判定方法

质数（Prime number），又称为素数，指的是在大于1的自然数中，除了1和该数本身外，无法被其他自然数整除的数（同样也可以定义为只有与该数本身及1两个正因数的数）。

关于如何快速判断一个数是否为质数，以及在给定区间内如何筛出所有的质数，这些都是大厂面试中常见的考察点。下面我们将对这两个问题进行简要的分析。

本文中所有函数参数均默认为自然数。我们将使用C++语言进行代码示例，并给出相应的缺省源码。

判断一个非负整数是否为质数：

根据质数的定义，我们可以编写相应的代码。该代码的时间复杂度和空间复杂度均在可接受范围内，并且适用于处理一定范围内的问题。

我们再观察一下合数通常会被哪些数筛掉，并列出相应的表格（记为表1）。通过对表1的观察，我们发现筛掉合数的数通常都是较小的质数。这让我们想到，如果一个数在较小的范围内没有非质因数，那么这个数是否可能就是质数呢？

接下来，我们考虑寻找合数的最小非因质数的上限。设合数为x，其最小非因质数为y，我们可以通过一定的数学推导得出y的上限范围。由于x是合数，它必然存在因数，而这些因数中必有一个是最小的非因质数。我们可以通过这个性质来进一步判断一个数是否为质数。

对于筛出区间内的所有质数，我们可以使用一种称为埃氏筛（Eratosthenes' sieve）的方法。这种方法的基本思想是从最小的质数开始枚举，标记其倍数作为合数，从而筛出区间内的所有质数。埃氏筛的时间复杂度和空间复杂度均较为优秀，是一种非常经典的筛法。

还有一种线性筛法（sieve of Euler）可以更加高效地筛出质数。这种方法可以方便地区分筛掉合数的两个数之间是否存在倍数关系，常用于筛积性函数。

图示中展示了质数数量pi(n)（蓝色曲线）、n / ln n（绿色曲线）以及Li(n)（红色曲线）。这些曲线可以帮助我们更直观地理解质数的分布情况。

既然可以用质数来判断一个数是否为合数，那么是否可以直接用质数来筛出合数呢？这样做确实可以减少不必要的计算。具体实现时，我们可以从最小的质数开始枚举，用isp[i]来表示之前是否已经被筛过。若枚举到一个未被筛过的数，则其为质数，并用它来筛去后面的合数。这种方法被称为埃氏筛法，是入门级筛法中非常经典的一种。

最后提到的线性筛法是一种更加高效的筛法方法。通过线性筛选的方法，我们可以更加方便地区分筛掉合数的两个数之间是否存在倍数关系。线性筛法的时间复杂度和空间复杂度均表现优异，是一种非常常用的筛法。