nth Prime Number Java

如果一个数只能被 1 和它本身整除，那么它就是素数。换句话说，素数是一个只有两个不同自然数因子（1 和它本身）的自然数。例如，2、3、5、7、11 等都是素数。请注意，0 和 1 不是素数。2 是唯一的偶素数，因为所有其他偶数都能被 2 整除。在本节中，我们将学习如何在 Java 中找到第 n 个素数。

有两种方法可以在 Java 中找到第 n 个 素数

• 使用基本/传统方法
• 使用埃拉托斯特尼筛法

使用基本/传统方法

在基本方法中，我们遵循与查找素数相同的方法。按照下面给出的步骤操作。

• 从用户那里读取一个整数（n）。
• 在 while 循环中，执行条件（c != n）。最初，变量 c 是 0，用于计算已找到的素数。
• 将变量 i（最初为 1）递增 1，以检查下一个数字。
• 检查变量 i 是否为素数。
• 如果是，则将变量 c 递增 1。

让我们通过一个使用 while 循环的 Java 程序来查找第 n 个素数。

NthPrimeNumberExample.java

输出 1

Enter the value of n to compute the nth prime number: 3
The 5th prime number is: 5

输出 2

Enter the value of n to compute the nth prime number: 25
The 25th prime number is: 97

我们从用户那里获取一个整数并将其存储在变量 n 中。while 循环继续，直到 count 变量的值小于 n。如果 while 循环返回 true，则变量 num 的值将增加 1。

之后，出现一个 for 循环，它以 i 初始化为 2 开始。for 循环执行，直到条件 i <= num 为 true。每次条件为 true 时，它都会将变量 num 除以 i，并将结果与 0 进行比较。如果结果等于 0，则循环中断并跳转到下一个语句，该语句将 i 与 num 进行比较。如果变量 i 等于 num，则将变量 count 的值递增 1。

之后，控制再次移至 while 循环。while 循环终止后，我们将获得第 n 个素数。

让我们用另一种方法来查找第 n 个素数。

使用埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种古老的算法，我们可以用它来查找指定数字（上限）以内的所有素数。它通过识别和标记每个素数的倍数来实现，从第一个素数 2 开始。当每个素数的倍数都被标记为合数（非素数）时，其余未标记的数字就是素数。这是查找小于 n 的所有素数的最有效方法（适用于 n < 10,000,000）。该方法使用 O(n) 的内存，时间复杂度为 O(nloglogn)。让我们看看应该采用什么方法。

方法

• 首先，使用埃拉托斯特尼筛法找到给定上限内的所有素数。
• 将所有素数存储在 Vector 中。
• 对于给定的数字 N，返回 Vector 中索引为 (N-1) 的元素。

算法

• 生成一个从 2 到 n 的连续整数列表。
• 最初，令 p = 2。我们认为第一个素数 2 是 p。
• 从 p^2 开始，以 p 的增量计数，并在列表中标记这些大于或等于 p^2 的数字。这些数字将是 p(p+1)、p(p+2)、p(p+3) 等。
• 在列表中找到大于 p 的第一个未标记的数字。如果没有这样的数字，则停止。否则，令 p 等于这个数字（这是下一个素数），然后从步骤 3 开始重复。

算法终止后，所有未标记的数字都是素数。

示例

让我们通过一个例子来理解上述方法。

假设我们要查找小于或等于 20（n）的所有素数。所以，我们需要打印所有小于或等于 n 的素数。让我们创建一个从 2 到 20 的数字列表。

在上表中，标记所有能被 2 整除的数字（我们已用红色标记），以及大于或等于其平方的数字。

在第一个素数（2）和未标记的数字之后，下一个未标记的数字是 3。现在我们将标记能被 3 整除的数字（我们已用蓝色标记），以及大于或等于其平方的数字。

表中下一个未标记的素数是 5，所以我们将标记能被 5 整除的数字，以及大于或等于其平方的数字。能被 5 整除的数字是 10、15 和 20，它们已经被标记了。因此，没有数字需要标记。

在上表中，未标记的数字是

因此，我们得到素数（2、3、5、7、11、13、17 和 19）。

NthPrimeNumber.java

输出

7th prime number is 17
22nd prime number is 79
10000th prime number is 104729