Right-Truncatable Prime in Java

右截断素数，无论从右到左顺序移除数字，都会保持其素数性质，最终剩下一个个位数素数。 739 满足右截断素数条件，因为当我们从 739 开始，依次得到 73，然后是 7，它们都是素数。高效检测右截断素数需要实现素数检测和递归或迭代来系统地移除数字。

朴素方法

验证右截断素数状态的过程首先通过高效方法（如试除法）进行素数测试。素数大于一，但其因子仅为一和它本身。

我们依次移除最后一个数字，然后进行字符串转换，再进行整数转换。每个截断后的值也必须是素数；如果其中任何一个不是素数，则该数字不是右截断素数。此过程一直持续到只剩下一个个位数素数。为了找到多个这样的素数，我们高效地遍历一个范围。

输出

 
Right-Truncatable Primes up to 1000:
[2, 3, 5, 7, 13, 17, 23, 37, 53, 73, 113, 137, 173, 197, 313, 317, 373, 797]   

解释

在上面的程序中，首先，我们定义了 isPrime() 函数，用于通过试除法测试小于或等于 n 的 素数。之后，另一个 isRightTruncatablePrime() 函数用于通过从右侧截断数字来评估剩余部分数字的素性。

findRightTruncatablePrimes 函数通过实现 isRightTruncatablePrime 执行的检查，遍历指定范围内的每个数字。如果数字符合右截断条件，则将其放入一个列表中。

基于筛法的实现

基于筛法的实现允许高效地进行素数检查，这对于找到右截断素数至关重要。此方法包括

1. 使用埃拉托斯特尼筛法预先计算素数（减少冗余的素性测试）。
2. 通过逐步移除最后一个数字并确保所有截断后的数字都保持素数来检查右截断性质。

输出

 
Right-Truncatable Primes:
2 3 5 7 23 29 31 37 53 59 71 73 79 233 239 293 311 313 317 373 379 593 599 719 733 739 797 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393 23333 23339 23399 23993 29399 31193 31379 37337 37339 37397 59393 59399 71933 73331 73939 233993 239933 293999 373379 373393 593933 593993 719333 739391 739393 739397 739399   

结论

右截断素数问题是数论中一个有趣的挑战，需要高效地检查一个数字在移除其最右边的数字时是否保持素数。最佳方法包括三个关键步骤。首先，高效的素性测试至关重要，可以使用试除法或预计算的筛法。

其次，采用贪婪的方法迭代地截断数字，并验证每个截断后的形式是否保持素数。最后，优化可以帮助减少冗余计算，例如缓存结果或在 2 之后跳过偶数。这个问题在数学研究、密码学和算法问题解决中有应用。