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

Answer 1

You can do this much more nicely. I reformated your code:

(define (prime? x)
  (define (prime-helper x k)
    (cond ((= x k) #t)
          ((= (remainder x k) 0) #f)
          (else
           (prime-helper x (+ k 1)))))
  (cond ((= x 1) #f)
        ((= x 2) #t)
         (else
          (prime-helper x 2))))

(define (primes-up-to n)
  (define (helper x)
    (cond ((= x 0) '())
          ((prime? x)
           (cons x (helper (- x 1))))
          (else
           (helper (- x 1)))))
  (reverse
    (helper n)))

scheme@(guile-user)> (primes-up-to 20)
$1 = (2 3 5 7 11 13 17 19)

Please don’t write Scheme like C or Java – and have a look at these style rules for languages of the lisp-family for the sake of readability: Do not use camel-case, do not put parentheses on own lines, mark predicates with ?, take care of correct indentation, do not put additional whitespace within parentheses.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.