SML: Basic Prime Testing

Question

I'm trying to write a basic function to take an integer and evaluate to a bool that will check whether the integer is a prime or not.

I've used an auxiliary function to keep track of the current divisor I'm testing, like so:

fun is_divisible(n : int, currentDivisor : int) =
    if currentDivisor <= n - 1 then
        n mod currentDivisor = 0 orelse is_divisible(n, currentDivisor + 1)
    else
        true;

fun is_prime(n : int) : bool =
    if n = 2 then
        true
    else
        not(is_divisible(n, 2));

It looks right to me but I test it on 9 and get false and then on 11 and get false as well.

Sorry for all the questions today and thanks!

Answer 1

The problem is that if your is_divisible reaches the last case it should return false because it means that all the iterated divisors have resulted in a remainder larger than zero except for the last one which is the number it self. So you should rename is_divisible and return false instead of true