In today’s Programming Praxis, our task is to enumerate all the non-palindrome prime numbers that are still prime when their digits are reversed. Let’s get started, shall we?

Since we are to focus on maximum speed, the obvious choice is to use a library.

import Data.Numbers.Primes

I tried a couple different versions, and settled on a simple filter. This version can calculate all the emirps under one million in about 650 ms. One other version where the isPrime test was replaced by first putting all the primes in a Set and doing membership testing was a fraction faster (about 10 ms), but it is about twice as long and requires specifying the maximum up front, which is less convenient then the current infinite stream. I also tried to make it faster via parallelism, but I could only get it to go slower, so it looks like the benefits of doing everything in parallel don’t weigh up against the additional overhead. Or maybe I’m just not using the library right.

emirps :: [Integer]
emirps = [p | p <- primes, let rev = reverse (show p)
, isPrime (read rev), show p /= rev]

All that’s left is to print all the emirps under a million.

main :: IO ()
main = print $ takeWhile (< 1000000) emirps

As mentioned, just evaluating the list takes about 650 ms, which is about the same as the Scheme version.

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, emirps, Haskell, kata, praxis, primes, programming

This entry was posted on November 2, 2010 at 1:14 pm and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

November 3, 2010 at 3:46 pm |

Hi,

You use the Data.Numbers.Primes package, but if you did your own prime numbers generation, would the bench be horrible ?

++ greg

November 3, 2010 at 6:35 pm |

That would depend on the algorithm used. Obviously a naive algorithm, like the one I used in the previous exercise, is going to be pretty slow. I tried using the basic wheel factorization method from http://bonsaicode.wordpress.com/2009/05/08/programming-praxis-%E2%80%93-wheel-factorization/ (Data.Numbers.Primes also relies on wheel factorization, albeit a more complex version) and it calculates the whole list in about 1.5 seconds. That’s on a different computer than the original solution though, so the two aren’t directly comparable. Still, it’s not too far off and that’s with an algorithm that hasn’t exactly been optimized for speed (for instance, my primes function was simply 2 : filter isPrime [3,5..]). So the short answer is no, it wouldn’t be a whole lot worse. But why bother reinventing the wheel (factorization)? :)

November 3, 2010 at 9:54 pm |

I was looking for comments/tips about an efficient implementation of the prime numbers generation, and you answered it well.

And I agree, no need to reinvent the wheel :D (good one ;))

Thanks again

Greg