Scheme prime numbers

Question

this is possibly much of an elementary question, but I'm having trouble with a procedure I have to write in Scheme. The procedure should return all the prime numbers less or equal to N (N is from input).

(define (isPrimeHelper x k)
  (if (= x k) #t
  (if (= (remainder x k) 0) #f
      (isPrimeHelper x (+ k 1)))))

(define ( isPrime x )
    (cond
      (( = x 1 ) #t)
      (( = x 2 ) #t)
      ( else (isPrimeHelper x 2 ) )))

(define (printPrimesUpTo n)
    (define result '())
    (define (helper x)
        (if (= x (+ 1 n)) result
        (if (isPrime x) (cons x result) ))
        ( helper (+ x 1)))
    ( helper 1 ))

My check for prime works, however the function printPrimesUpTo seem to loop forever. Basically the idea is to check whether a number is prime and put it in a result list.

Thanks :)

Solution 1

First, it is good style to express nested structure by indentation, so it is visually apparent; and also to put each of if's clauses, the consequent and the alternative, on its own line:

(define (isPrimeHelper x k)
  (if (= x k) 
      #t                           ; consequent
      (if (= (remainder x k) 0)    ; alternative
  ;; ^^ indentation
          #f                               ; consequent
          (isPrimeHelper x (+ k 1)))))     ; alternative

(define (printPrimesUpTo n)
    (define result '())
    (define (helper x)
        (if (= x (+ 1 n)) 
            result                  ; consequent
            (if (isPrime x)         ; alternative
                (cons x result) ))         ; no alternative!
        ;; ^^ indentation
        ( helper (+ x 1)))
    ( helper 1 ))

Now it is plainly seen that the last thing that your helper function does is to call itself with an incremented x value, always. There's no stopping conditions, i.e. this is an infinite loop.

Another thing is, calling (cons x result) does not alter result's value in any way. For that, you need to set it, like so: (set! result (cons x result)). You also need to put this expression in a begin group, as it is evaluated not for its value, but for its side-effect:

    (define (helper x)
        (if (= x (+ 1 n)) 
            result        
            (begin 
                (if (isPrime x) 
                    (set! result (cons x result)) )   ; no alternative!
                (helper (+ x 1)) )))

Usually, the explicit use of set! is considered bad style. One standard way to express loops is as tail-recursive code using named let, usually with the canonical name "loop" (but it can be any name whatever):

(define (primesUpTo n) 
  (let loop ((x n) 
             (result '())) 
    (cond 
      ((<= x 1) result)      ; return the result
      ((isPrime x) 
            (loop (- x 1) (cons x result)))   ; alter the result being built
      (else (loop (- x 1) result)))))         ; go on with the same result

which, in presence of tail-call optimization, is actually equivalent to the previous version.

Solution 2

You have several things wrong, and your code is very non-idiomatic. First, the number 1 is not prime; in fact, is it neither prime nor composite. Second, the result variable isn't doing what you think it is. Third, your use of if is incorrect everywhere it appears; if is an expression, not a statement as in some other programming languages. And, as a matter of style, closing parentheses are stacked at the end of the line, and don't occupy a line of their own. You need to talk with your professor or teaching assistant to clear up some basic misconceptions about Scheme.

The best algorithm to find the primes less than n is the Sieve of Eratosthenes, invented about twenty-two centuries ago by a Greek mathematician who invented the leap day and a system of latitude and longitude, accurately measured the circumference of the Earth and the distance from Earth to Sun, and was chief librarian of Ptolemy's library at Alexandria. Here is a simple version of his algorithm:

(define (primes n)
  (let ((bits (make-vector (+ n 1) #t)))
    (let loop ((p 2) (ps '()))
      (cond ((< n p) (reverse ps))
            ((vector-ref bits p)
              (do ((i (+ p p) (+ i p))) ((< n i))
                (vector-set! bits i #f))
              (loop (+ p 1) (cons p ps)))
            (else (loop (+ p 1) ps))))))

Called as (primes 50), that returns the list (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47). It is much faster than testing numbers for primality by trial division, as you are attempting to do. If you must, here is a proper primality checker:

(define (prime? n)
  (let loop ((d 2))
    (cond ((< n (* d d)) #t)
          ((zero? (modulo n d)) #f)
          (else (loop (+ d 1))))))

Improvements are possible for both algorithms. If you are interested, I modestly recommend this essay on my blog.

Solution 3

The (if) expression in your (helper) function is not the tail expression of the function, and so is not returned, but control will always continue to (helper (+ x 1)) and recurse.

Solution 4

The more efficient prime?(from Sedgewick's "Algorithms"):

(define (prime? n)
  (define (F n i) "helper"
    (cond ((< n (* i i)) #t)
          ((zero? (remainder n i)) #f)
          (else
           (F n (+ i 1)))))
 "primality test"
 (cond ((< n 2) #f)
     (else
      (F n 2))))

View more solutions

Comments

[GeneralFailure]

Aaah i see. So in the if when i do that check = x (+ 1 n) if it is true then i should exit the function. Something like return statement. Is there such a statement in scheme

[Dolda2000]

You don't need a return statement, though. Simply only execute (helper (+ x 1)) if (= x (+ 1 n)) is false; that is, in your case, as part of the second (if) expression.