这个问题是在采访中问的（关于素数）
Russian Doll Primes
它们通常被称为可截断素数。
我在Wiki上找到了此代码
public static void main(String[] args){
final int MAX = 1000000;
//Sieve of Eratosthenes (using BitSet only for odd numbers)
BitSet primeList = new BitSet(MAX>>1);
primeList.set(0,primeList.size(),true);
int sqroot = (int) Math.sqrt(MAX);
primeList.clear(0);
for(int num = 3; num <= sqroot; num+=2)
{
if( primeList.get(num >> 1) )
{
int inc = num << 1;
for(int factor = num * num; factor < MAX; factor += inc)
{
//if( ((factor) & 1) == 1)
//{
primeList.clear(factor >> 1);
//}
}
}
}
//Find Largest Truncatable Prime. (so we start from 1000000 - 1
int rightTrunc = -1, leftTrunc = -1;
for(int prime = (MAX - 1) | 1; prime >= 3; prime -= 2)
{
if(primeList.get(prime>>1))
{
//Already found Right Truncatable Prime?
if(rightTrunc == -1)
{
int right = prime;
while(right > 0 && primeList.get(right >> 1)) right /= 10;
if(right == 0) rightTrunc = prime;
}
//Already found Left Truncatable Prime?
if(leftTrunc == -1 )
{
//Left Truncation
String left = Integer.toString(prime);
if(!left.contains("0"))
{
while( left.length() > 0 ){
int iLeft = Integer.parseInt(left);
if(!primeList.get( iLeft >> 1)) break;
left = left.substring(1);
}
if(left.length() == 0) leftTrunc = prime;
}
}
if(leftTrunc != -1 && rightTrunc != -1) //Found both? then Stop loop
{
break;
}
}
}
System.out.println("Left Truncatable : " + leftTrunc);
System.out.println("Right Truncatable : " + rightTrunc);
}
这给出了输出：
Left Truncatable : 998443
Right Truncatable : 796339
但是我无法解决这个特殊的俄罗斯玩偶素数问题，例如，如果您有素数，并且删除了该素数的左数或右数，那么该结果数是否是素数？
我对此并不陌生，所以请原谅任何错误。
最佳答案
让我们从头开始：
根据您提供的问题链接：
“俄罗斯娃娃素是
素数，其右数位可以重复删除，并且是
还是素数。”
我假设您有一个函数boolean isPrime(int)来确定数字是否为质数。
谷歌搜索，我们从Wikipedia中发现，可以右截断的质数的数目最多为73,939,133，该数目为83，这使蛮力成为可行的选择；但可以在此处采用一些优化技术：
由于我们进行了右截断，因此我们可以安全地消除偶数（因为任何偶数都不是素数，因此在其上生成的任何数字都绝不会是俄罗斯娃娃素数）。
由于任何以5开头的数字都可以被5整除，因此根据我在前面提到的相同规则，我们可以消除5。
剩下的数字包含1、3、7和9。
现在，如果我们想生成这四个数字的所有可能组合，且不超过您提到的最大值（1,000,000），则只需进行4,096次迭代。
这种技术的缺点是我们现在有4,096个数字，其中包含可能的非素数，或者由非素数形成的素数，因此不是俄罗斯玩偶素数。我们可以通过遍历并检查这些数字来消除它们。或者更好的是，我们可以更仔细地研究俄罗斯娃娃的素数。
在检查了我从上面的链接中引用的规则后，我们发现俄罗斯玩偶素数是素数，其右位数字可以重复删除，并且仍然是素数（因此仍然是俄罗斯玩偶素数，反复给定单词）！
这意味着我们可以使用最小的一位俄罗斯玩偶素数进行运算，也可以使用上面使用的生成魔术，并且由于由俄罗斯玩偶素数形成的任何素数都是俄罗斯玩偶素数，因此我们可以消除非素数尽早产生了俄罗斯玩偶素数的完整清单，同时大大减少了此类程序的运行时间。
看一下下面的生成代码：
void russianDollPrimesGeneration(int x) {
x *= 10;
if (x * 10 >= 1000000) return;
int j;
for (int i=1; i<=9; i+=2) {
if (i == 5) continue;
j = x + i;
if (isPrime(j)) {
addToRussianDollPrimesList(j);
russianDollPrimesGeneration(j);
}
}
}
前提是
void addToRussianDollPrimesList(int x)是一个将x添加到我们先前保存的用于存储俄语娃娃素数的列表的函数。更新说明
请注意，您可以在
void russianDollPrimesGeneration(int x)函数的if条件内调用对void addToRussianDollPrimesList(int x)的调用，因为每当调用前一个函数时，我们总是会使用相同的参数来调用后一个函数。我在这里将它们分开以强调生成函数的递归性质。另请注意，您必须使用整数0运行此函数。
最后要注意的是，在许多情况下，即使上面的生成函数
void russianDollPrimesGeneration(int x)是Russian Doll Prime，也不会算在内。还记得我们省略2和5时，因为偶数和被5除的数不能是素数，所以俄罗斯娃娃素数也不能吗？因此不能组成俄罗斯娃娃素体？好吧，这种情况不适用于2和5，因为它们是素数，并且由于它们是个位数，因此它们是俄罗斯娃娃素数，并且如果放在左边（如23），则有资格形成俄罗斯娃娃素数和53。
那么，如何更正我们的代码以包括这些特殊情况呢？
我们可以创建一个包装函数，将这两个数字相加并检查可以使用它们形成的Russian Doll Prime（这与我们上面使用的生成函数相同）。
void generationWrapperFunction(int x) {
addToRussianDollPrimesList(2);
russianDollPrimesGeneration(2);
addToRussianDollPrimesList(5);
russianDollPrimesGeneration(5);
russianDollPrimesGeneration(0);
}
结束更新说明
这个小功能将产生一个俄罗斯娃娃素数列表，然后可以在其中搜索我们要寻找的数字。
以下递归函数是一个替代方法，但我认为它将更耗时：
boolean isRussianDollPrime(int n) {
if (!isPrime(n)) return false;
if (n < 10) return true;
return isRussianDollPrime(n / 10);
}
可以修改此函数以使用可左截断的素数。但是，对于左截短的素数，基于世代的解决方案将很难实施。
关于java - 俄罗斯娃娃素，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25227098/