C++

Forum

 
Performance issue when trying to find Palindromic Primes

BryanTriana (18)
I am trying to find a way to make the function pn_pal() to work faster, currently it takes a long time to find the highest palindromic prime when the number is 7 digits or above. The function pn_pal() is working with atkinsieve() a function that uses the atkin sieve algorithm to find primes and pal_test() that tests if a given number is a palindrome.

pn_pal():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
unsigned long long inpalprime::pn_pal(unsigned long long n)
{
   unsigned long long pal
 //finds the highest palindromic prime equal or less than n
    for(std::vector<bool>::size_type it=atkinsieve(n).size()-1; it!=1; it--)
    {
        if(atkinsieve(n)[it] && pal_test(it))
        {
            pal=it;
            break;
        }
    }
    
    
    return pal;
}


atkinsieve():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
std::vector<bool> inpalprime::atkinsieve(unsigned long long m)
{
    std::vector<bool> p_test(m+1, false);
    
    //defines square root of n
    unsigned long long root=ceil(sqrt(m));
    
    //sieve axioms
    for(unsigned long long x=1; x<=root; x++)
    {
        for(unsigned long long y=1; y<=root; y++)
        {
            unsigned long long i=(4*x*x)+(y*y);
            if (i<=m && (i%12==1 || i%12==5))
            {
                p_test[i].flip();
            }
            i=(3*x*x)+(y*y);
            if(i<=m && i%12==7)
            {
                p_test[i].flip();
            }
            i=(3*x*x)-(y*y);
            if(x>y && i<=m && i%12==11)
            {
                p_test[i].flip();
            }
        }
    }
    
    //marks 2,3,5 and 7 as prime numbers
    p_test[2]=p_test[3]=p_test[5]=p_test[7]=true;
    
    //marks all multiples of primes as non primes
    for(unsigned long long r=5; r<=root; r++)
    {
        if((p_test[r]))
        {
            for(unsigned long long j=r*r; j<=m; j+=r*r)
            {
                p_test[j]=false;
            }
        }
    }
    
    
    return p_test;
}


pal_test():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
bool inpalprime::pal_test(unsigned long long n)
{
   std::string ull; 
//converting m to a string
    ull=std::to_string(n);
    
    //checking if the characters of ull match their reverse
    for(unsigned long long i=0; i<ull.length()/2; i++)
    {
        if(ull[i]!=ull[ull.length()-i-1])
        {
            return false;
        }
    }
    
    return true;
}
Duthomhas (13212)
You're actually doing it the hard way around.

Construct odd palindromes, and test those for primality.

For anything less than nine digits or so a simple trial-divisions primality test will do. If you wish to handle larger numbers then you'll want to implement a Miller-Rabin test, which isn't too difficult, but it takes 40 to 50 lines of code across several functions (not counting the limited trial-divisions test you should first do).

Testing with a sieve is a brilliant idea, but it is not computationally efficient.

Hope this helps.
ne555 (10692)
> currently it takes a long time
¿how much is a long time? ¿what improvement do you need?

Your algorithm seems to be O(n) or a little worse.
Now you have these issues:
- Compute all the primes to N
- Traverse all the range from N to the previous prime
I guess that the sieve is taking the most part of the time, but you may improve both:
- Compute the primes with the sieve only to sqrt(N). Traverse the sieve and save the primes in a vector. Then to test for primality use trial division agains your prime list.
- Traverse only palindromic numbers. You can form them as 'db' or 'dxb' where 'd' is the reverse of 'b'
Topic archived. No new replies allowed.