Finding a prime number in Scheme using natural recursion

Question

I'm still plugging away at the exercises in How to Design Programs on my own, but have managed to get stuck again. This time it's question 11.4.7:

Develop the function is-not-divisible-by<=i. It consumes a natural number [>=1], i, and a natural number m, with i < m. If m is not divisible by any number between 1 (exclusive) and i (inclusive), the function produces true; otherwise, its output is false.

Use is-not-divisible-by<=i to define prime?, which consumes a natural number and determines whether or not it is prime.

The first part I didn't have too hard a time with:

;; A natural number [>=1] is either 1. 1 or 
;; 2. (add1 n) where n is a natural number [>=1].

;; is-not-divisible-by<=i : N[>=1] N -> boolean
(define (is-not-divisible-by<=i i m)
  (cond
    [(= i 1) true]
    [else (cond
            [(= (remainder m i) 0) false]
            [else (is-not-divisible-by<=i (sub1 i) m)])]))
(is-not-divisible-by<=i 3 6) ; expected: false.
(is-not-divisible-by<=i 6 7) ; expected: true.

But I just can't see how I can use one variable to do this while using natural recursion. I thought about using a list, but that presents the same problems.

The only solution I can see is giving another variable--let's say x-- the same value as n, and then just doing it the way is-not-divisible-by<=i does it. But I think the authors intend for me to do it some other, simpler way. (And I don't even know how to do what I described anyway, haha.)

This problem has really been busting my butt, so any help or hints, if you could, would be great!

Answer 1

A prime number is a number that cannot be divided by any number smaller than itself. You have already implemented the "cannot be divided by any number smaller than" part:

(define (prime? n)
  (is-not-divisible-by<=i (sub1 n) n))