title: Finding a prime number in Scheme using natural recursion
body: <p>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:</p>
  
  <blockquote>
    <p>Develop the function
    is-not-divisible-by&lt;=i. It consumes a
    natural number [>=1], i, and a natural
    number m, with i &lt; m. If m is not
    divisible by any number between 1
    (exclusive) and i (inclusive), the
    function produces true; otherwise, its
    output is false. </p>
    
    <p>Use is-not-divisible-by&lt;=i to define
    prime?, which consumes a natural
    number and determines whether or not
    it is prime.</p>
  </blockquote>
  
  <p>The first part I didn't have too hard a time with:</p>
  
  <pre><code>;; A natural number [&gt;=1] is either 1. 1 or 
  ;; 2. (add1 n) where n is a natural number [&gt;=1].
  
  ;; is-not-divisible-by&lt;=i : N[&gt;=1] N -&gt; boolean
  (define (is-not-divisible-by&lt;=i i m)
    (cond
      [(= i 1) true]
      [else (cond
              [(= (remainder m i) 0) false]
              [else (is-not-divisible-by&lt;=i (sub1 i) m)])]))
  (is-not-divisible-by&lt;=i 3 6) ; expected: false.
  (is-not-divisible-by&lt;=i 6 7) ; expected: true.
  </code></pre>
  
  <p>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. </p>
  
  <p>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&lt;=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.)</p>
  
  <p>This problem has really been busting my butt, so any help or hints, if you could, would be great!</p>