CODEWITHSUNDEEP
recursionracket
James Callaway
James Callaway

Reputation: 15

Finding a prime number in Scheme using natural recursion

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!

Upvotes: 0

Views: 12452

Answers (3)

Sergio Maass
Sergio Maass

Reputation: 3

It is not necessary that you divide all of the numbers from n-1 to 2 to check primality. You only need to check from (floor (sqrt n)). So a faster aproach (specially for large numbers), that also takes care about the undefined (prime? 1) problem, is:

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

Upvotes: 0

joe
joe

Reputation: 11

(prime? 1) gets a "division by zero" error.

here is a modified version of the original code. It takes care of (prime? 1) problem for now.

(define (prime? p)
  (define (non-divisible-by n d)
    (cond
     ((= d 1) #t)
     (else (if(= (remainder n d) 0)
          #f
          (non-divisible-by n (- d 1))))))
  (if (= p 1)
      #t
      (non-divisible-by p (- p 1))))

Now (prime? 1) returns #t

Upvotes: 1

Victor Nicollet
Victor Nicollet

Reputation: 24577

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))

Upvotes: 3

Related Questions