Left -Truncatable Prime in Java

什么是左截断素数？

在数论中，左截断素数是一种特殊的素数，当其最高位数字被依次移除时，剩余的数字仍然是素数。

换句话说，如果我们截断一个左截断素数的最高位数字，得到的数字仍然是一个素数。这个过程可以重复进行，直到只剩下一个个位数素数。它在OEIS序列 A024785 中定义。

同样，在数论中，也有右截断素数和左右截断素数。

左截断素数示例

317 是一个左截断素数，因为

• 移除最高位数字：17 (仍然是素数)。
• 移除下一个最高位数字：7 (仍然是素数)。

其他一些左截断素数有：2, 3, 5, 7, 13, 17, 23, 37, 53, 73, 113, 137, 173, 197, 233, 313, 317, 373, 797, 3137, 3797, ……。

请注意，总共有 **4260 个左截断 素数**。最后一个（第 4260 个）左截断素数是 357686312646216567629137。

寻找左截断素数

• 从一个潜在的素数开始：选择一个我们要检查的数字；它可能是一个左截断素数。确保该数字没有前导零。
• 检查给定数字是否为素数：这确保了初始数字是素数。
• 重复移除最高位数字：如果给定的数字是素数，则截断（移除）第一个数字，并检查剩余的数字是否也是素数。重复此步骤，直到得到一个单数字。
• 如果所有截断的数字都是素数，则它是左截断素数：如果通过截断最高位数字生成的每个数字都是素数，则给定的数字是左截断素数。

Java 程序查找左截断素数

输出

 
2, 3, 5, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 103, 107, 113, 137, 167, 173, 197, 223, 283, 307, 313, 317, 337, 347, 353, 367, 373, 383, 397, 443, 467,    

解释

在上面的程序中，我们定义了一个方法来检查一个数字是否为素数 (isPrime)，以及另一个 方法 来检查一个数字是否为左截断素数 (isLeftTruncatablePrime)。然后它遍历直到定义的限制的数字，并打印出左截断素数。

您可以根据需要定义自己的限制来查找更多的左截断素数。

复杂度

时间复杂度：O(N*N)

辅助空间：O(N)