algorithm - 这个难题的更有效实现是什么？

Question

谜题

对于每个输入数 n (n < 10) 都有一个输出数 m 使得:

• m的第一个数字是n
• m是n位数字
• m内的每2位序列必须是不同的素数

输出应为 m，其中 m 是满足上述条件的最小数字。如果没有这个数字，输出应该是-1；

例子

n = 3 -> m = 311

n = 4 -> m = 4113(注意这不是 4111，因为那会重复 11)

n = 9 -> m = 971131737

我的可行解决方案

这是我的第一次尝试，“蛮力”方法。我正在寻找一种更优雅的解决方案，因为随着 n 变大，这种方法效率非常低。

public long GetM(int n)
{
    long start = n * (long)Math.Pow((double)10, (double)n - 1);
    long end = n * (long)Math.Pow((double)10, (double)n);
    for (long x = start; x < end; x++)
    {
        long xCopy = x;
        bool allDigitsPrime = true;
        List<int> allPrimeNumbers = new List<int>();
        while (xCopy >= 10)
        {
            long lastDigitsLong = xCopy % 100;
            int lastDigits = (int)lastDigitsLong;
            bool lastDigitsSame = allPrimeNumbers.Count != 0 && allPrimeNumbers.Contains(lastDigits);
            if (!IsPrime(lastDigits) || lastDigitsSame)
            {
                allDigitsPrime = false;
                break;
            }

            xCopy /= 10;
            allPrimeNumbers.Add(lastDigits);
        }

        if (n != 1 && allDigitsPrime)
        {
            return x;
        }
    }

    return -1;
} 

关于如何提高效率的初步想法

因此，显然这里的瓶颈是遍历可以满足此条件的整个数字列表，从 n.... 到 (n+1)....。不是简单地增加循环的每次迭代的次数，而是必须有一些巧妙的方法来根据 2 位序列必须是质数的要求来跳过数字。例如对于 n = 5，通过 50000 - 50999(50 不是素数)、51200 - 51299(12 不是素数)是没有意义的，但我不太确定如何实现或者是否可以实现足以使算法运行 n=9 的优化。

关于这种方法或不同的优化方法有什么想法吗？

Answer 1

您不必尝试所有数字。您可以改为使用不同的策略，总结为“尝试附加数字”。

哪个数字？嗯，这样的数字

1. 它与你当前的最后一位数组成一个质数
2. 形成的质数在之前的数中没有出现过

这应该递归地(而不是迭代地)完成，因为您可能会用完选项，然后您必须回溯并尝试数字中更早的不同数字。

这仍然是一个指数时间算法，但它避免了大部分搜索空间，因为它从不尝试任何不符合每对相邻数字必须构成素数规则的数字。