recursionschemeracketprimesprimality-test

Check for a prime number using recursive helper function


I am trying to check if a number is prime using recursion. I was required to use a recursive helper function, but I am not sure how I should implement it.

I think I know the algorithm, but I've never tried to use a recursive helper function in Racket. This is my current thoughts:

  1. See if n is divisible by i = 2
  2. Set i = i + 1
  3. If i^2 <= n continue.
  4. If no values of i evenly divided n, then it must be prime.

This is what I have so far...

(define (is_prime n)
  (if (<= n 1)
      #f
      (if (= (modulo n 2) 0)
          #f

)

What would be a good approach using a recursive helper function??

Thanks!


Solution

  • Using a helper simply means that you should split your program in smaller parts, and possibly encapsulate loops with extra parameters in separate procedures - and in Scheme loops are frequently implemented via recursive calls. One (naïve) way to implement the is_prime procedure would be:

    (define (is_prime n)
      (cond ((<= n 1) #f)
            ((= n 2) #t)
            ((= (modulo n 2) 0) #f)
            (else (check 3 n))))
    
    ; recursive helper
    (define (check i n)
      (cond ((> (* i i) n) #t)
            ((= (modulo n i) 0) #f)
            (else (check (+ i 2) n))))
    

    There are many ways to implement this procedure, and many possible optimizations; the above should be enough get you started.