Posts Tagged ‘emirps’

Programming Praxis – Emirps

November 2, 2010

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.