So lets start at the beginning, Dominic Penfold initially posed the problem and gave an efficient algorithm implemented in C++ (39 lines):

bool IsPrime(int num) { int sqrt = 1 + sqrtf(num); for (int i=2; i<sqrt; i++) { if (num % i == 0) return false; } return true; } int NthLeftTruncatablePrime(int target) { std::vector<int> PrimeRoots; PrimeRoots.push_back(2); PrimeRoots.push_back(3); PrimeRoots.push_back(5); PrimeRoots.push_back(7); int start = 0; int tens = 10; while(true) { int end = PrimeRoots.size(); for (int i=1; i<10; i++) { for (int pos = start; pos< end; pos++) { int newprime = tens * i + PrimeRoots[pos]; if (IsPrime(newprime)) { PrimeRoots.push_back(newprime); if (PrimeRoots.size()==target) return newprime; } } } start = end; tens *= 10; } }

Performance was considerably faster when 32-bit integers were switched for 64-bit integers.

The C++ code is very easily converted into C# (35 lines):

static bool IsPrime(int num) { int sqrt = 1 + (int ) System.Math.Sqrt(num); blue">for (int i = 2; i < sqrt; i++) { if (num % i == 0) return false; } return true; } static int NthLeftTruncatedPrime(int target) { var primeRoots = new List<int>() { 2, 3, 5, 7}; int start = 0; int tens = 10; while (true) { int end = primeRoots.Count; for (int i = 1; i < 10; i++) { for (int pos = start; pos < end; pos++) { int newprime = tens * i + primeRoots[pos]; if (IsPrime(newprime)) { primeRoots.Add(newprime); if (primeRoots.Count == target) return newprime; } } } start = end; tens *= 10; } }

Conversion to F# is only slightly trickier as there is no equivalent return statement, but similar behavior can be accomplished using yield (30 lines):

let IsPrime n = if n = 1 then false else let max = n |> float |> sqrt |> int let rec Test = function | x when x > max -> true | x -> if (n % x) = 0 then false else Test (x+1) Test 2 let NthLeftTruncatablePrime n = let oneDigitPrimes = [2;3;5;7] seq { let primes = ref oneDigitPrimes for tens = 1 to 8 do let acc = ref [] for i=1 to 9 do let newPrime = i * pown 10 tens let primes' = ref !primes while (!primes').Length > 0 do let x = newPrime+(!primes').Head if IsPrime x then acc := x :: !acc yield x primes' := (!primes').Tail done done primes := !acc |> List.rev done } |> Seq.append oneDigitPrimes |> Seq.nth (n-1)

The extra overhead of generating a sequence can be avoided using instead recursion (25 lines including IsPrime function):

let NthLeftTruncatablePrime index = let rec Find digit factor primes primes' count acc = match digit, primes' with | 10, _ -> let primes = List.rev acc Find 1 (10*factor) primes primes count [] | _, [] -> Find (digit+1) factor primes primes count acc | _, prime::tail -> let k = (digit * factor) + prime let count, acc = if IsPrime k then count+1, k::acc else count, acc if count = index then k else Find digit factor primes tail count acc let primes = [2;3;5;7] if index <= 4 then List.nth primes (index-1) else Find 1 10 primes primes 4 []

Later Matt Curran (coincidentally another ex-games developer) got in on the act with a Haskell version (17 lines including a comment – although the lines are a little dense):

```
isPrime :: Int -> Bool
isPrime 1 = False
isPrime x = null $ take 1 [n | n <- [2..upperBound x], 0 == mod x n]
where
upperBound = floor . sqrt . fromIntegral
-- list of all left truncatable primes
ltps :: [Int]
ltps = ps 1 [0]
where
ps _ [] = []
ps m prevMag = thisMag ++ (ps (m*10) thisMag)
where
thisMag = primes [x*m | x <- [1..9]] prevMag
where
primes [] _ = []
primes (m:mgs) bases =
(filter isPrime [m+x | x <- bases]) ++ (primes mgs bases)
```

**Results Breakdown by language**

Language | Lines of code | Performance(ms) |

C++ | 39 | 5.213 |

C# | 35 | 5.332 |

F# sequence | 30 | 14.075 |

F# recursive | 25 | 5.412 |

Haskell | 17 | ? |

LeftTruncatablePrime.cpp (1.45 kb)

LeftTruncatablePrime.cs (1.58 kb)

LeftTruncatablePrime_seq.fs (1.53 kb)

LeftTruncatablePrime_rec.fs (1.36 kb)

## No comments:

Post a Comment