Java 中的欧几里得-穆林序列

欧几里得-穆林数列是一个数学数列，由质数组成，其特点是递归定义。更技术性地说，这个数列以数字 2 作为其第一项。后续项是通过查找满足特定条件的质数来生成的。在这个数列中，每一项的新项都是最小的质数。当你用它除以前一项然后加 1 时，结果是另一个质数。

以下是该过程更技术性的概述

1. 数列的第一项始终是 2。
2. 要确定下一项，请查找大于前一项的最小质数，该质数除以前一项并加 1 后，结果是质数。
3. 该过程将迭代地继续以生成更多项。

示例 1

输入： N = 20

输出

2 3 7 43 13 53 5 6221671 38709183810571 139 2801 11 17 5471 52662739 233 2207 1746860020068409 761 5403705334863907824909

示例 2

输入： N = 5

输出

2 3 7 43 13

示例 3

输入： N = 8

输出

2 3 7 43 13 53 5 6221671

方法：贪心算法

在欧几里得-穆林数列中，贪心算法通过反复查找 (1 + product) 的最小质因数来工作，其中 product 是数列前各项的乘积。它是数列中的下一项。然后，算法使用下一项更新 product 变量。该过程将继续，直到生成所需的项数。

算法

1. 创建一个名为“findSmallestPrimeFactor”的方法，该方法接受 BigInteger 整数“num”作为输入。
2. 将 BigInteger 变量 `i` 初始化为 2。
3. 使用 while 循环查找 `num` 的最小质因数
   1. 确定 'i * i' 是否小于或等于 'num'。
   2. 如果 `num` 可被 `i` 整除（即 `num` 模 `i` 为零），则返回 `i` 作为最小质因数。
   3. 将 `i` 增加一。
4. 如果没有找到更小的因数，则返回 `num` 本身作为最小质因数。
5. 创建一个名为 `generateEuclidMullinSequence` 的方法，该方法接受 BigInteger `N` 作为输入。
6. 将 BigInteger 变量 `product` 初始化为 1，以跟踪前各项的乘积。
7. 将 BigInteger 变量 `termCounter` 初始化为 0，以计算生成的项数。
8. 使用 while 循环生成并打印数列的前 N 项
   1. 使用 `findSmallestPrimeFactor` 方法计算当前项，即 `(1 + product)` 的最小质因数。
   2. 打印当前项。
   3. 如果与上一项不同，则打印一个空格。
   4. 通过将当前项与其相乘来更新 product。
   5. 将项计数器加一。
9. 在 `main` 方法中，使用名为 `numberOfTerms` 的 BigInteger 变量设置要生成的项数（在本例中为 14）
10. 调用 `generateEuclidMullinSequence` 方法并传入 `numberOfTerms`，以生成并显示欧几里得-穆林数列的前 14 项。

实施

文件名： EuclidMullinSequence.java

输出

Euclid-Mullin Sequence: 2 3 7 4313535 6221671 38709183810571 139 280111 17 5471

时间复杂度： 该代码的时间复杂度约为 O(N * sqrt(num))，其中 N 是欧几里得-穆林数列中要生成的项数。

辅助空间： 该代码的辅助空间复杂度为 O(1)，这意味着它使用的内存量是恒定的，不随输入大小而变化。