如何判断一个数是否是质数

判断一个数 $n$（$n > 1$）是否为质数，可以使用以下几种常见方法：

试除法

这是最基本的方法。从 $2$ 开始，一直到 $\sqrt{n}$

​ 为止，用每个整数 $i$ 去除 $n$，如果 $n$ 能被 $i$ 整除（即 $n \bmod i = 0$），那么 $n$ 就不是质数；如果在这个范围内都不能整除，那么 $n$ 就是质数。

例如判断 $19$ 是否为质数：

计算 $\sqrt{19} \approx 4.36$

​≈4.36。

用 $2$ 到 $4$ 依次去除 $19$：

$19 \div 2 = 9 \cdots \cdots 1$（余数为 $1$，不能整除）。

$19 \div 3 = 6 \cdots \cdots 1$（余数为 $1$，不能整除）。

$19 \div 4 = 4 \cdots \cdots 3$（余数为 $3$，不能整除）。

 

由于在 $2$ 到 $\sqrt{19}$

​ 这个范围内没有数能整除 $19$，所以 $19$ 是质数。

埃拉托色尼筛法（适用于判断一定范围内的质数）

如果要找出小于等于 $N$ 的所有质数，可以使用这种方法。步骤如下：

创建一个布尔数组 $isPrime$，长度为 $N + 1$，初始值都设为 $true$，表示假设所有数都是质数。

将 $0$ 和 $1$ 对应的 $isPrime[0]$ 和 $isPrime[1]$ 设为 $false$，因为 $0$ 和 $1$ 不是质数。

从 $2$ 开始，遍历到 $\sqrt{N}$

​：

如果 $isPrime[i]$ 为 $true$，说明 $i$ 是质数。

然后将 $i$ 的倍数（从 $i \times i$ 开始，因为 $2i, 3i, \cdots, (i - 1)i$ 在之前已经被标记过了）对应的 $isPrime$ 数组位置设为 $false$，表示这些数不是质数。

 

遍历结束后，$isPrime$ 数组中值为 $true$ 的索引位置对应的数就是质数。

例如找出小于等于 $30$ 的所有质数：

初始化 $isPrime$ 数组，$isPrime[0] = false$，$isPrime[1] = false$，其余为 $true$。

从 $2$ 开始：

$isPrime[2] = true$，将 $2 \times 2 = 4$，$2 \times 3 = 6$，$2 \times 4 = 8$，$\cdots$，$2 \times 15 = 30$ 对应的 $isPrime$ 位置设为 $false$。

 

接着看 $3$：

$isPrime[3] = true$，将 $3 \times 3 = 9$，$3 \times 4 = 12$，$\cdots$，$3 \times 10 = 30$ 对应的 $isPrime$ 位置设为 $false$。

 

再看 $4$，由于 $isPrime[4] = false$，跳过。

看 $5$：

$isPrime[5] = true$，将 $5 \times 5 = 25$ 对应的 $isPrime$ 位置设为 $false$。

 

当遍历到 $\sqrt{30} \approx 5.48$

​≈5.48 时结束。

最终，$isPrime$ 数组中值为 $true$ 的索引 $2$、$3$、$5$、$7$、$11$、$13$、$17$、$19$、$23$、$29$ 就是小于等于 $30$ 的质数。