Print first N prime numbers in Common Lisp

Tag: printing , numbers , lisp , primes , clisp Author: cheayu123 Date: 2013-03-19

I am making a Common Lisp function to print the first N prime numbers. So far I've managed to write this code:

;globals 
(setf isprime 1) ;if 1 then its a prime, 0 if not.
(setf from 1)    ;start from 1
(setf count 0)   ;should act as counter to check if we have already 
                 ;    N primes printed

;function so far.
(defun prime-numbers (to)
  (if (> count to) nil(progn
      (is-prime from from)
      (if (= isprime 1) (print from)(setf count (+ count 1)))
      (setf isprime 1)
      (setf from (+ from 1))
      (prime-numbers to)))
  (if (>= count to)(setf count 0) (setf from 1)))  

;code to check if a number is prime    
(defun is-prime(num val)
  (if (< num 3) nil 
    (progn
      (if (= (mod val (- num 1)) 0) (setf isprime 0))
      (is-prime (- num 1) val))))

My problem is, it does not print N primes correctly. If I call >(prime-numbers 10), results are: 1 2 3 5 7 11 13 17 19 1, i.e. it printed only 9 primes correctly.

but then if i call >(prime-numbers 2) the results are: 1 2 3 5 7 1

what am I doing wrong here?? this is my first time to code in LISP.

UPDATE:

  (defparameter from 1)
  (defparameter count 0)

  (defun prime-numbers (to)
     (if (> count to)nil
         (progn
            (when (is-prime from) 
                (print from)
                (setf count (+ count 1)))
            (setf from (+ from 1))
            (prime-numbers to)))
     (when (>= count to)
         (setf count 0) 
         (setf from 1)))  

  (defun is-prime (n)
    (cond ((= 2 n) t)
     ((= 3 n) t)
     ((evenp n) nil)
     (t 
       (loop for i from 3 to (isqrt n) by 2
             never (zerop (mod n i))))))

works fine. but outputs a NIL at the end.

Best Answer

First, there's no need to use globals here, at all.

Use true/false return values. That would allow your is-prime function to be something like:

(defun is-prime (n)
  (cond ((= 2 n) t) ;; Hard-code "2 is a prime"
        ((= 3 n) t) ;; Hard-code "3 is a prime"
        ((evenp n) nil) ;; If we're looking at an even now, it's not a prime
        (t ;; If it is divisible by an odd number below its square root, it's not prime
           (loop for i from 3 to (isqrt n) by 2
                 never (zerop (mod n i))))))

That way, the function is not relying on any external state and there's nothing that can confuse anything.

Second, the last 1 you see is (probably) the return value from the function.

To check that, try: (progn (prime-numbers 10) nil)

Third, re-write your prime-numbers function to not use global variables.

Fourth, never create global variables with setf or setq, use either defvar or defparameter. It's also (mostly, but some disagree) good style to use *earmuffs* on your global (really, "special") variables.

comments:

you can use always in your loop instead of return-from.
@sds True. It's been a few years since I wrote loops in anger and return-from was within trivial reach.
@sds Rewritten using never.
thank you for this!. but I still don't have the required outputs. besides the globals. what could be wrong with my prime-numbers?
@binaryjc I actually think using globals is causing your problem. Using global state for communicating between functions is close to the best way of making your code not work there is.

Other Answer1

To expand on Vatines answer:

A possible rewrite of the prime-numbers function, using the same algoritm but avoiding globals is

(defun prime-numbers (num &optional (from 2))
   (cond ((<= num 0) nil)
         ((is-prime from) (cons from (prime-numbers (1- num) (1+ from))))
         (t (prime-numbers num (1+ from)))))

This function also returns the primes instead of printing them.

The problem with this recursive solution is it consumes stack for each prime found/tested. Thus stack space may be exhausted for large values of num.

A non-recursive variant is

(defun prime-numbers (num &optional (start 2))
   (loop for n upfrom start
         when (is-prime n)
         sum 1 into count
         and collect n
         until (>= count num)))