Java 中将数字字符串拆分为素数

给定一个仅包含数字的字符串，该字符串表示一个数字。我们的任务是以一种方式拆分这个数字字符串，使得拆分后形成的每个数字段都是一个素数。此外，我们还需要最小化拆分次数。请注意，如果输入字符串本身表示一个素数，则最小拆分次数为 1，因为我们将其视为一个整体。找到的素数必须在 1 到 10^6 的范围内。让我们通过一些例子来理解这一点。

示例 1

输入 "13477317"

输出 2

解释：如果我们进行 1 次拆分，那么我们将 13477317 视为一个整体，数字 13477317 可以被 3 整除。因此，无法进行 1 次拆分。现在，我们进行 2 次拆分，发现 13477 是一个素数，317 也是一个素数。因此，在 2 次拆分后，我们得到了所有段都是素数。

示例 2

输入 "17"

输出 1

解释：如果我们进行 1 次拆分，那么我们将 17 视为一个整体，数字 13477317 是一个素数。因此，1 次拆分就足够了。

让我们看看查找拆分的不同方法。

使用递归

核心思想是考虑最多 6 位数的每个前缀（因为已知素数小于 10^6），并验证它是否是素数。如果是素数，则递归调用方法来验证剩余的字符串。如果任何组合未能给出适当的排列，则会在控制台上显示一条适当的消息。

文件名：SplitStringPrimes.java

输出

For the number 343, the minimum number of splits is: 2
For the number 37, the minimum number of splits is: 1
For the number 44, the minimum number of splits is not possible.
For the number 367555, the minimum number of splits is: 4

复杂度分析

上述程序的 time complexity 为 O(N^{5 / 2})，其中 O(N²) 时间用于递归查找所有可能的组合。由于我们还需要检查数字是否为素数，这项任务的时间复杂度为 O(N^{1 / 2})。因此，上述程序的总时间复杂度为 O(N²) * O(N^{1 / 2}) = O(N^{5 / 2})，其中 N 是输入字符串中的总位数。

使用迭代

使用迭代，可以通过动态规划来解决此问题。

我们可以定义一个数组 splitArr[]，并使用它，其中 splitArr[q] 表示长度为“q”的前缀字符串拆分为素数子集所需的最小拆分数。

数组 splitArr[] 的填充方式如下：

• 使用一个循环来遍历输入字符串的所有索引。
• 对于上述循环中的每个索引 'q'，开始另一个从 1 到 6 的循环，以检查从 (p + q) 索引开始的子字符串是否构成一个素数。
• 如果形成一个素数，则数组 splitArr[] 中的值可以更新为：splitArr [p + q] = min(splitArr[p + q], 1 + splitArr[p]);

当所有值都更新后，最后一个索引处的值就是我们的答案，因为它包含了整个输入字符串的最小拆分数。

文件名：SplitStringPrimes1.java

输出

For the number 343, the minimum number of splits is: 2
For the number 37, the minimum number of splits is: 1
For the number 44, the minimum number of splits is not possible. 
For the number 367555, the minimum number of splits is: 4

复杂度分析

上述程序的 time complexity 为 O(N^{3 / 2})，其中 O(N) 时间用于遍历所有索引。我们还需要检查数字是否为素数，这项任务的时间复杂度为 O(N^{1 / 2})。因此，上述程序的总时间复杂度为 O(N) * O(N^{1 / 2}) = O(N^{3 / 2})，其中 N 是输入字符串中的总位数。

我们知道此问题中的素数范围是从 1 到 10^6。我们可以利用此信息进行进一步优化。通过预先计算素数检查并将结果存储在数组中，可以实现进一步优化。预先计算可以使用埃拉托斯特尼筛法进行。请注意以下程序。

文件名：SplitStringPrimes2.java

输出

For the number 343, the minimum number of split is: 2
For the number 37, the minimum number of split is: 1
For the number 44, the minimum number of split is not possible. 
For the number 367555, the minimum number of split is: 4

复杂度分析

这是最优化的方法，因为上述程序的 time complexity 为 O(N)，其中 N 是输入字符串中的总位数。尽管计算筛法的时间复杂度为 O(N * log(N))，但我们可以忽略它，因为它只计算一次。因此，与其他程序不同，我们可以在 O(1) 时间内检查一个数字是否为素数。