CODEWITHSUNDEEP
recursionf#functional-programmingprimesprimality-test
Overly Excessive
Overly Excessive

Reputation: 2125

Prime number check

I'm having some issues with my prime number checker in F#. It doesn't seem to give the right results so I'm guessing I've screwed up the logic somewhere but I can't figure out where. The implementation is a simple brute forcing one so the logic isn't complicated and I've implemented similiar solutions using for loops in imperative languages before.

let rec isPrime iterator (n : int) = 
                            match iterator with
                            | 1 -> isPrime (iterator + 1) n
                            | a when a = n -> isPrime (iterator + 1) n
                            | _ -> match n % iterator = 0 with
                                    | true -> false
                                    | false -> isPrime (iterator + 1) n

Upvotes: 0

Views: 744

Answers (1)

Tomas Petricek
Tomas Petricek

Reputation: 243096

As you already figured out in the comments, the problem is that the function should terminate and say true when the iterator reaches n. You can actually make it faster just by iterating up to square root of n or at least n/2 because by the time you reach n/2, you know it will be a prime.

This kind of logic seems to be easier to write using if rather than match - although you can easily fix it by fixing the case in match, I'd probably write something like:

let rec isPrime iterator (n : int) = 
  if iterator = n / 2 then true
  elif iterator = 1 then isPrime (iterator + 1) n
  elif n % iterator = 0 then false
  else isPrime (iterator + 1) n

Also, you might not want to expose the iterator parameter to the user - you can write the code using a nested function which calls the loop starting with iterator = 2 (and then you don't need the iterator = 1 case at all):

let isPrime (n : int) = 
  let rec loop iterator = 
    if iterator = n/2 then true
    elif n % iterator = 0 then false
    else loop (iterator + 1)
  loop 2

Upvotes: 3

Related Questions