Super Prime in Java

超级素数是一个素数，它在所有素数的序列中占据一个素数的位置。例如，在列表 {2, 3, 5, 7, 11} 中，第二个素数 (3) 和第三个素数 (5) 是超级素数。识别超级素数需要素数生成和索引。

示例

输入： N = 10

输出 3, 5, 11

解释

对于输入 N = 10，我们首先找出所有小于等于 10 的素数，即 {2, 3, 5, 7}。然后，我们查看它们在列表中的位置：第 1 个素数是 2，第 2 个是 3，第 3 个是 5，第 4 个是 7。

接下来，我们确定哪些位置本身是素数。素数位置是 2、3 和 5。因此，我们选择这些位置的素数：3（第 2 个素数）、5（第 3 个素数）和 11（第 5 个素数）。因此，N = 10 的超级素数是 3、5 和 11。

方法 1：使用素数索引

算法

步骤 1：理解问题： 超级素数是位于所有素数序列的素数索引处的素数。例如，在素数序列 {2, 3, 5, 7, 11} 中，位置 2、3、5（1 基索引）处的素数是 {3, 5, 11}，它们是超级素数。

步骤 2：生成 N 以内的素数： 使用埃拉托斯特尼筛法找出给定限制 N 以内的所有素数。创建一个布尔数组 isPrime[]，其中每个索引代表一个数字是否为素数。最初，除 0 和 1 外，将所有数字标记为素数。对于从 2 开始的每个数字 p，将 p 的所有倍数标记为非素数。将所有标记为素数的数字添加到素数列表中。

步骤 3：识别素数索引： 步骤 2 中生成的素数序列是带索引的。例如，{2, 3, 5, 7, 11} 的索引为 1、2、3、4、5。找出本身是素数的索引，例如 2、3、5。

步骤 3.1：检查素数索引： 在此步骤中，我们需要确定素数列表中的哪些索引本身是素数。为此，我们检查每个索引（从 2 开始）是否为素数。如果索引是素数，我们将其添加到素数索引列表中。这些素数索引将帮助我们识别超级素数所在的位置。

步骤 4：提取超级素数： 使用步骤 3 中获得的素数索引，在素数列表中获取这些位置处的素数。这些就是超级素数。

步骤 4.1：检索素数位置处的素数： 在此步骤中，我们使用前面确定的素数索引列表从生成的列表中获取相应的素数。对于每个素数索引，我们访问素数列表中该位置处的素数。这些选定的素数是超级素数，因为它们在素数序列中占据素数位置。

步骤 5：返回结果： 识别出超级素数后，将结果显示或返回。这包括打印出作为素数序列中素数位置处的素数的超级素数列表，或返回该列表以供程序进一步处理或测试。

输出

 
Super Primes: [3, 5, 11, 17]   

复杂度分析

时间复杂度

使用埃拉托斯特尼筛法生成素数的时间复杂度为 O(N log(log(N)))，其中 N 是上限。生成素数后，识别超级素数涉及检查素数索引，其复杂度为 O(P)，其中 P 是找到的素数数量。

空间复杂度

此方法的空间复杂度为 O(N)，其中 N 是上限。这是因为埃拉托斯特尼筛法需要大小为 N+1 的数组来标记素数。此外，存储素数列表需要与找到的素数数量成比例的空间，即 O(P)。

方法 2：使用双筛高效识别超级素数

算法

步骤 1：理解超级素数： 超级素数是所有素数序列中位于本身是素数的位置的素数。例如，在序列 {2, 3, 5, 7, 11} 中，第 2、3 和第 5 个位置的素数是超级素数。

步骤 1.2：分析超级素数概念： 超级素数是通过查找所有素数序列中占据素数位置的素数而得出的。例如，在序列 {2, 3, 5, 7, 11} 中，第 2、3 和第 5 个位置的素数是超级素数。它涉及双层素数识别。

步骤 2：生成 N 以内的所有素数： 使用埃拉托斯特尼筛法生成 N 以内的所有素数。此步骤确保我们拥有该范围内的完整素数列表。

步骤 2.1：高效素数生成： 要识别 N 以内的所有素数，请应用埃拉托斯特尼筛法。创建一个初始值为 true 的布尔数组，表示潜在的素数。从 2 开始，将每个素数的倍数标记为非素数。将仍标记为素数的数字收集到列表中以供进一步处理。

步骤 3：埃拉托斯特尼筛法的步骤： 创建一个大小为 N+1 的布尔数组 isPrime[]，所有索引（除 0 和 1 外）均初始化为 true（因为 0 和 1 不是素数）。

从第一个素数 p=2 开始。将 pp 的所有倍数（从 p² 开始）标记为非素数。对数组中的下一个未标记数字重复此过程，直到 p² 大于 N。将所有仍标记为 true 的数字添加到素数列表中。

步骤 4：预计算索引的素数标志： 确定素数列表中的哪些索引（1 基索引）是素数。这是通过生成 1 到素数列表大小的数字的布尔数组 isPrime 来完成的。使用相同的埃拉托斯特尼筛法技术，但这次将筛法限制在素数列表的大小。

步骤 4.1：识别素数索引： 使用埃拉托斯特尼筛法预先计算素数列表（1 基索引）中的哪些索引是素数。为 1 到素数列表大小的数字创建一个布尔数组。标记非素数索引，仅留下素数索引以有效识别超级素数。

步骤 5：查找超级素数： 遍历素数列表。对于每个素数，使用步骤 3 中创建的 isPrime[] 数组检查其 1 基索引是否为素数。如果索引是素数，则将相应素数添加到超级素数列表中。

步骤 6：输出超级素数： 识别出超级素数后，打印或返回列表。这些是在 N 以内的所有素数序列中位于素数位置处的素数。

文件名：SuperPrimeEfficient.java

输出

 
Super Primes: [3, 5, 11, 17]   

复杂度分析

时间复杂度

此方法的时​​间复杂度为 O (N log (log(N)))，用于使用埃拉托斯特尼筛法生成素数，其中 N 是上限。检查素数索引会增加 O(P)，其中 P 是 N 以内的素数计数。总而言之，时间复杂度为 O(N log (log(N))+P)。

空间复杂度

空间复杂度为 O(N)，用于埃拉托斯特尼筛法，因为它使用大小为 N+1 的布尔数组来标记素数。此外，存储素数列表需要 O(P) 的空间，其中 P 是 N 以内的素数数量。因此，总空间复杂度为 O(N+P)。