Since I first posted an F# solution to Left-Truncatable Primes, C# and Haskell have entered the frame, and although this is not a good problem for a serious comparison of languages, I think it is still interesting.

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 trick

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

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 | ? |

Note: the time is to generate the 1000th prime, and the same computer was used for all tests, as was release mode. Haskell time coming soon.

LeftTruncatablePrime.cpp (1.45 kb)

LeftTruncatablePrime.cs (1.58 kb)

LeftTruncatablePrime_seq.fs (1.53 kb)

LeftTruncatablePrime_rec.fs (1.36 kb)

This article has been translated to Serbo-Croatian language by WHGeeks .