How can I generate prime palindromes in a given range without complete searching it and using a check function?

Question

I have seen previous solutions to this problem, but it is all complete search with a check function and not fast enough for me.

I am working on a C++ program trying to generate all prime palindromes highly efficiently in a given range of integers. For the prime part, I have created a fast primality tester by cutting down on divisors I test by eliminating all multiples of 2 and 3, though suggestions for improvement here would also be appreciated (function pasted below).

My main issue is that I need to generate palindromes fast enough without using the conventional complete search and palindrome test that slowly increments the tested integer. My current search code and primality test are pasted below.

I have tried to increment the digits of a number in the middle then the outer ones, but because over time more digits are added over time I couldn't even piece together an algorithm.

Primality Test:

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

Palindrome Test + Main Function

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

String conversions are not only slow, but put pressure on the memory allocator. This is a big issue if you are performing lots of queries.

Instead, you can use math to reverse the digits. All you do is pull each digit off the right-hand side of your number and add it to the right-hand side of another number:

e.g.

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

Notice that by step 3 we can already determine that the number will not be a palindrome, because the "reversed" value has become greater than the remaining value.

The code might look something like this:

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

Note that the check in the middle of the loop catches the case where the number of digits in the palindrome is odd.

This will help improve performance. And if you really want a speed boost then you should use something like the Sieve of Eratosthenes. Provided you know the maximum value required for prime testing, you can generate the prime table extremely fast.

Here's a quick and dirty implementation. It's not very memory efficient, but it's simple to write. You're welcome to make it use less memory by condensing the data to bits and removing all even entries. That will reduce the memory consumption by a factor of 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;
};

Now, if you have a sieve already computed, then your prime test actually becomes way faster than your palindrome test. So you only need to call it as many times as there are prime numbers. With that approach, you can generate lots of palindromic primes rather quickly:

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

---

Results, after some experiments

I did a little bit of basic testing, and found to my surprise that using the sieve for prime-testing is actually overkill here, and leads to worse performance -- at least when searching the entire space once.

Because the actual number of palindromic primes is very small compared to the number of primes, it seems there's better efficiency by first using the fast palindrome test, and then performing the naive prime-test if required.

On my computer, searching the first 1 billion integers (to find 5953 total palindromic primes), I get the following results:

Using sieve approach:

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

Using naive approach:

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