如何在给定范围内生成素数回文而不完全搜索它并使用检查函数？

Question

我已经看到过这个问题的以前的解决方案，但它都是带有检查功能的完整搜索，对我来说不够快。

我正在开发一个 C++ 程序，试图在给定的整数范围内高效地生成所有素数回文。对于主要部分，我通过消除 2 和 3 的所有倍数来减少我测试的除数，从而创建了一个快速素数测试器，不过这里的改进建议也将受到赞赏（函数粘贴在下面）。

我的主要问题是我需要足够快地生成回文，而不使用传统的完整搜索和回文测试来缓慢增加测试的整数。我当前的搜索代码和素性测试粘贴在下面。

我尝试增加中间数字的数字，然后增加外部数字的数字，但是因为随着时间的推移，会添加更多的数字，我什至无法拼凑出一个算法。

素性测试：

bool CheckPrime(int n){
    switch (n) {
    case 1: return false;  break;
    case 2: return true;  break;
    case 3: return true;  break;
    default: break;
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

回文测试+主要函数

bool CheckPalindrome (int n) {
    string temp = to_string(n);
    reverse(temp.begin(), temp.end());
    if (temp.compare((to_string(n))) == 0) {
        return true;
    }
    else {
        return false;
    }
}


int main() {
int L, R; cin >> L >> R;
vector <int> Palindromes;
for (int i = L; i <= R; i++) {
    if (CheckPalindrome(i)) {
        Palindromes.push_back(i);
    }
}
}

Answer 1

字符串转换不仅慢，而且会给内存分配器带来压力。如果您执行大量查询，这是一个大问题。

相反，您可以使用数学来反转数字。您所要做的就是从号码右侧取出每个数字并将其添加到另一个号码的右侧：

例如

Step      Value     Digit     Reversed
0         12345     -         0
1         1234      5         5
2         123       4         54
3         12        3         543
4         1         2         5432
5         0         1         54321

请注意，通过步骤 3，我们已经可以确定该数字将不是回文数，因为“反转”的值已变得大于剩余值。

代码可能看起来像这样：

bool CheckPalindrome(unsigned int value)
{
    unsigned int reverse = 0;
    while (value > reverse)
    {
        reverse = reverse * 10 + value % 10;
        if (value == reverse) return true;
        value /= 10;
    }
    return value == reverse;
}

请注意，循环中间的检查捕获回文数中的位数为奇数的情况。

这将有助于提高性能。如果你真的想要提高速度，那么你应该使用埃拉托斯特尼筛之类的东西。如果您知道素数测试所需的最大值，您就可以非常快速地生成素数表。

这是一个快速而肮脏的实现。它的内存效率不是很高，但编写起来很简单。欢迎您通过将数据压缩为位并删除所有偶数条目来使其使用更少的内存。这将使内存消耗减少 16 倍。

class PrimeSieve
{
public:
    PrimeSieve(unsigned int maxval)
    {
        isPrime.resize(maxval, 1);
        isPrime[0] = isPrime[1] = 0;
        for(unsigned int i = 2; i < maxval; i++)
        {
            if (!isPrime[i]) continue;
            for(int x = i *2; x < maxval; x += i) isPrime[x] = 0;
        }
    }

    bool operator[](unsigned int value) const
    {
        return isPrime[value] != 0;
    }

    unsigned int size() const {
        return isPrime.size();
    }

private:
    std::vector<char> isPrime;
};

现在，如果您已经计算了一个筛子，那么您的素数测试实际上会比回文测试快得多。所以你只需要调用它与素数一样多的次数。通过这种方法，您可以相当快地生成大量回文素数：

int main()
{
    PrimeSieve sieve(100000000);
    for (unsigned int i = 1; i < sieve.size(); i++)
    {
        if (sieve[i] && CheckPalindrome(i))
        {
            std::cout << i << " is a palindromic prime.\n";
        }
    }
}

经过一些实验后的结果

我做了一些基本测试，令我惊讶的是，使用筛子进行素数测试实际上是多余的，并且会导致性能更差——至少在搜索整个空间一次时是这样。

由于回文素数的实际数量与素数的数量相比非常小，因此首先使用快速回文测试，然后在需要时执行朴素素数测试似乎效率更高。

在我的计算机上，搜索前 10 亿个整数（找到 5953 个回文素数），得到以下结果：

使用筛法：

Generating prime table: 14.374s
Searching palindromic primes: 1.138s
Total search using sieve: 15.513s

使用天真的方法：

Searching palindromic primes: 9.206s
Total search with naive prime calculation: 9.206s