primes.lsp
 Version 1.00    31 October 2004
 Author   Steven Jones

 Contact jones57@swbell.net include the word "nyquist" in subject line

 The contents of this file are released under the terms of the GNU General
 Public License. See the file LICENSE.txt

 Provides primeality test and list of primes less then 1000.

function

 (isprime n)
 Primality test

 n      - NUMBER. The numeric value to be tested. If n is negative or zero 
          the result is nil. If n is a float and may be represented by an 
          integer it is converted to an integer prior to testing. Floats 
          which may not be represented by an integer return nil. 

 return - BOOL.

con

 List of primes less then 1000

function

 (factor n)
 Return the prime factors of a numnber.

 n      - NUMBER. If n is 0 the result is (incorrectly) 0. If n is a float 
          and may not be represented by an intger an error is raised. 
          Flotas which may be representd as intgers are converted prior 
          to testing. Minus values return -1 as one of the factors.

 return - LIST.

;; primes.lsp
;; Version 1.00    31 October 2004
;; Author   Steven Jones
;;
;; Contact jones57@swbell.net include the word "nyquist" in subject line
;; 
;;
;; The contents of this file are released under the terms of the GNU General
;; Public License. See the file LICENSE.txt
;;
;; Provides primeality test and list of primes less then 1000.
;;

(provide 'primes)
(current-file "primes")


;; @doc function isprime
;; (isprime n)
;; Primality test
;;
;; n      - NUMBER. The numeric value to be tested. If n is negative or zero 
;;          the result is nil. If n is a float and may be represented by an 
;;          integer it is converted to an integer prior to testing. Floats 
;;          which may not be represented by an integer return nil. 
;;
;; return - BOOL.
;;

(defun isprime (n)
  (cond ((minusp n) 'nil)
	((= 1 n) 'nil)
	((floatp n)
	 (if (/= (truncate n) n) 'nil
	   (isprime (truncate n))))
	((and (zerop (rem n 2))(/= n 2)) 'nil)
	(t (do ((m (+ (truncate (sqrt (float n))) 1))
		(c 3 (+ c 2))
		(done 'nil)
		(rs 't))
	       ((or done (>= c m)) rs)
	     (if (zerop (rem n c))
		 (setq done 't
		       rs 'nil))))))


;; @doc con +PRIMES+
;; List of primes less then 1000
;;

(setq +PRIMES+ '())
(do ((n 1 (+ n 1)))
    ((> n 1000))
  (if (isprime n)
      (setq +PRIMES+ (cons n +PRIMES+))))
(setq +PRIMES+ (reverse +PRIMES+))


;; @doc function factor
;; (factor n)
;; Return the prime factors of a numnber.
;;
;; n      - NUMBER. If n is 0 the result is (incorrectly) 0. If n is a float 
;;          and may not be represented by an intger an error is raised. 
;;          Flotas which may be representd as intgers are converted prior 
;;          to testing. Minus values return -1 as one of the factors.
;;
;; return - LIST.
;;

(defun factor (n)
  (cond ((and (floatp n)(= (truncate n) n))
	 (factor (truncate n)))
	((minusp n)
	 (cons -1 (factor (abs n))))
	((zerop n)
	 (list 0))
	((= 1 n)
	 (list 1))
	(t
	 (let ((rs '())
	       (m 3))
	   (do ()
	       ((not (zerop (rem n 2))))
	     (setq rs (cons 2 rs)
		   n (/ n 2)))
	   (do ()
	       ((= n 1))
	     (if (zerop (rem n m))
		 (setq rs (cons m rs)
		       n (/ n m))
	       (setq m (+ m 2))))
	   rs))))