A Simple Program for Finding Palindromic Prime Numbers

A palindromic prime (palprime) is a prime number that is also palindromic. So out of curiosity I wrote a simple program a few days ago that can find the palindromic numbers within a given range. Here is the code in C++:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <iostream>

using namespace std;

bool IsPrime(unsigned long long n) {
	bool r = true;

	for (unsigned long long i = 3; i < sqrt((double) n) + 1; i+= 2)
	{
		if (n % i ==0) {
			r = false;
			break;
		}
	}

	return r;
}

bool IsPalindrome(unsigned long long n) {
	bool r = true;
	char s[30];
	int l = sprintf(s, "%llu", n);

	if (l == 1 && n != 1) {
		r = true;
	} else	{
		for (int i = 0; i < l/2; i++) {
			if (s[i] != s[l-i-1]) {
				r = false;
				break;
			}
		}
	}

	return r;
}

/*
 * usage: palprime [lbound] [ubound] 
 */
int main(int argc, char** argv) {
	unsigned long long beginNum = 3;
	unsigned long long endNum = 3;

	if (argc == 2) { // lbound default to 3
#ifdef _WIN32
		endNum = _strtoui64(argv[1], NULL, 10);
#else
		endNum = strtoull(argv[1], NULL, 10);
#endif
		
	} else if (argc == 3) {
#ifdef _WIN32
		beginNum = _strtoui64(argv[1], NULL, 10);
		endNum = _strtoui64(argv[2], NULL, 10);
#else
		beginNum = strtoull(argv[1], NULL, 10);
		endNum = strtoull(argv[2], NULL, 10);
#endif
	}

        unsigned long long i = beginNum;

        while (i < endNum) {
                char s[30];
                int l = sprintf(s, "%llu", i);

		//length cannot be even as even length palindrome numbers
		//can be divided by 11.
                if (l % 2 == 0) {
                    i = ((unsigned long long) (i / 10)) * 100 + 1;
                    continue;
                }

		if (IsPalindrome(i)) {
			if (IsPrime(i)) {
				cout << i << endl;
			}
		}

                i+=2;

                if (s[0] % 2 == 0) {
                    i+=pow(10, l-1);

		    //leading/ending number cannot be 5
                    if (((int) (s[0] - '0')) + 1 == 5) {
                        i += 2 * pow(10, l-1);
                    }
                }
	}
	return (EXIT_SUCCESS);
}

At first, I was trying to find all the palprimes that can be represented by 64 bit integers. But soon I realized that it would take months to do so using the code above with a quad-core PC (using 4 processes with different ranges). Anyway, here’s the last few palindromic primes less than 10,000,000,000,000:

9999899989999
9999901099999
9999907099999
9999913199999
9999919199999
9999938399999
9999961699999
9999970799999
9999980899999
9999987899999

And here are a few interesting ones:

11357975311
1112345432111
1300000000031
1700000000071
1900000000091
7900000000097
9200000000029
1357900097531

Be Sociable, Share!

Leave a Reply