CODEWITHSUNDEEP
c++optimizationpalindromememory-efficient
SBM
SBM

Reputation: 103

Is there a more efficient way to generate Palindromes which are prime if the bounds are large?

I have solved this problem on USACO training about generating prime palindromes between a limit.I have quoted the problem transcript at the end. I solved it by generating all odd palindromes below the upper limit and checking each for prime printed them. The solution passed on the grader but is there an even efficient method than my noob generate all and check thing(for I really wish to learn more efficient strategies in competitive programming).

The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .

PROGRAM NAME: pprime

INPUT FORMAT

Line 1: Two integers, a and b SAMPLE INPUT (file pprime.in)

5 500

OUTPUT FORMAT

The list of palindromic primes in numerical order, one per line. SAMPLE OUTPUT (file pprime.out)

5
7
11
101
131
151
181
191
313
353
373
383

I guess I should also provide my algorithm for getting the output

Step 1. Take Input a and b
Step 2. Initialise a list of odd palindromes op
Step 3. Add 5, 7 and 11 to op
Step 4. Generate all the 3,5,7 digit odd palindromes and add to op
Step 5. Check for every element e of op
        Step 5.1. If e>=a and e<=b 
                  Step 5.1.1. If e is PRIME print e
        Terminate the loop otherwise

Had the upper bound been larger this process would obviously have failed, therefore I am looking for a more efficient solution.

EDIT: I check for primes the usual way, as in

Given the number I've to check for prime is n.
if (n==1) return false;
if (n==2) return true;
for (int i = 2; i <= sqrt(n); ++i)
    if (n%i == 0) return false;
return true;

Upvotes: 0

Views: 527

Answers (1)

Brooke Jackson
Brooke Jackson

Reputation: 166

Actually the way you checked for primality is quite efficient for small numbers, for checking the primality of bigger number, you can use primality tests, such as the Rabin Miller and the Baillie-PSW (BPSW or BSW) primality test. The thing is, those algorithm really looks magic, I've never even tried to understand how and why they work, but they do work pretty well ! With the later, I've been able to generate a 320 digits prime. You can easily find implementation of those algorithms online.

Upvotes: 1

Related Questions