java - 俄罗斯娃娃总理

Question

这个问题在一次采访中被问到(关于素数)
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

但是我无法解决这个特殊的俄罗斯娃娃素数问题，比如如果你有一个素数并且你删除了这个素数的左数或右数，那么结果数字是否是素数？

我是新手，所以请原谅任何错误。

Answer 1

让我们从头开始:

根据您提供的问题链接:

"Russian Doll Primes are prime numbers whose right digit can be repeatedly removed, and are still prime."

我假设你有一个函数 boolean isPrime(int)找出一个数是否是素数。

谷歌搜索，我们会从 Wikipedia 找到最多 73,939,133 个可右截断的素数为 83，这使得暴力破解成为一种可行的选择；但是这里可以使用一些优化技术:

由于我们右截断，我们可以安全地消除偶数(因为任何偶数都不会是素数，因此任何生成的数都不会是俄罗斯娃娃素数)。

由于任何以 5 开头的数都可以被 5 整除，那么根据我在上一点提到的相同规则，我们可以消除 5。

这给我们留下了包含 1、3、7 和 9 的数字。

现在，如果我们想生成这 4 个数字的所有可能组合，且不超过您提到的最大值(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)我们在 void addToRussianDollPrimesList(int x) 中的 if 条件中创建的函数，因为每当我们调用前一个函数时，我们总是会用相同的参数调用后一个函数。我在这里将它们分开是为了强调生成函数的递归性质。

另请注意，您必须使用整数 0 运行此函数。

最后一点是，在许多情况下，生成函数 void russianDollPrimesGeneration(int x)以上不算数，即使它们是俄罗斯娃娃 Primes。

还记得我们省略了 2 和 5 的时候，因为偶数和除以 5 的数字不能是质数，所以也不能是俄罗斯娃娃质数吗？并因此不能形成俄罗斯娃娃 Primes？好吧，这种情况不适用于 2 和 5，因为它们是质数，并且由于它们是个位数，因此它们是俄罗斯娃娃质数，并且如果放在左侧，则有资格形成俄罗斯娃娃质数，例如 23和 53。

那么如何更正我们的代码以包含这些特殊情况呢？

我们可以创建一个包装函数，将这两个数字相加，并检查可以使用它们形成的俄罗斯娃娃素数(这将与我们上面使用的生成函数相同)。

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);
}

可以修改此函数以使用可左截断的素数。然而，对于左截断素数，基于生成的解决方案将很难实现。