1.简介

在本教程中，我们将展示使用Java生成质数的各种方法。

如果您想检查数字是否为质数，请参阅以下快速指南。

2.质数

让我们从核心定义开始。 素数是大于1的自然数，除一个数本身以外，没有除数。

例如，7是质数，因为1和7是其唯一的正整数因子，而12并不是因为它除1、4和6外还具有除数3和2。

3.生成素数

在本节中，我们将看到如何有效地生成小于给定值的质数。

3.1。 Java 7及更低版本–蛮力

3.4。 使用Eratosthenes筛

还有另一种有效的方法可以帮助我们有效地生成质数，它被称为Eratosthenes筛。 它的时间效率为O(n logn)。

让我们看一下该算法的步骤：

创建一个从2到n的连续整数列表：(2，3，4，…，n)

最初，令p等于2，第一个素数

从p开始，以p为增量递增计数，并在列表中将这些数字中的每个数字标记为大于p本身。 这些数字将是2p，3p，4p等。 请注意，其中一些可能已被标记

在未标记的列表中找到大于p的第一个数字。 如果没有这样的数字，请停止。 否则，让p现在等于该数字(这是下一个质数)，然后从步骤3开始重复

当算法终止时，列表中所有未标记的数字都是质数。

代码如下所示：