How to determine prime number

Question

I'm trying to write a program using the OCaml language, but am experiencing problems utilizing nested functions. Here's the code I wrote:

let prime : int -> bool
= fun x ->
  if x > 2 then
    let a = x - 1 in
      let rec checkZero a x =
        if a > 1 then
          match x mod a with
           0 -> false
          |_ -> checkZero (a - 1) x
        else if a = 1 then
          true
  else if x = 2 then
    true
  else
    false
;;

To briefly explain my code, I'm using a nested function called checkZero to determine whether or not x is divisible by a value a which starts at x - 1 and goes down until 2.

After performing pattern matching, if the result of the mod operation is 0, then x is not a prime number, and if the result is anything else then we subtract 1 from a and perform checkZero again.

The particular error message that I'm getting is that I'm getting a syntax error where the double semicolons are.

I'm not too familiar with how OCaml works, but I do know that double semicolons are used when you want the entire code to be an expression. I'm not entirely sure what is causing the error, though.

Answer 1

I figured out that problem and feel rather silly now that I've seen it. I hope it helps anybody else struggling with similar issues.

As @glennsl has stated in the comment on the question, one thing I was missing is that "let ... in must be followed by an expression that invokes it." The problem with my code is that the checkZero function was not performing as I intended due to the lack of invocation.

Another thing that I realized is that rather than using if ... then ... else ... statements, it's more convenient to perform pattern matching at times.

Here's the code I came up with that works (if there are any errors in the code, please feel free to let me know):

let prime : int -> bool
= fun x ->
  match x with
     0 -> false
   | 1 -> false
   | _ -> let a = (x - 1) in
            let rec checkZero a x =
              if (a > 1) then
                match x mod a with
                   0 -> false
                 | _ -> checkZero (a - 1) x
              else
                true
              in
              checkZero a x
;;

An equivalent version without using the conditional statements is:

let prime : int -> bool
= fun n ->
  match n with
     0 -> false
   | 1 -> false
   | _ -> let a = (n - 1) in
            let rec checkZero a n =
              match a with
                 1 -> true
               | _ -> match n mod a with
                         0 -> false
                       | _ -> checkZero (a - 1) n
              in
              checkZero a n
;;