;;; primes.scm -- Jens Axel Søgaard ; (primes m) returns the list of all primes in the range 2 to m. ; This was written to show the use of the priority queues ; in priority-queue.scm. (require (planet "priority-queue.scm" ("soegaard" "galore.plt"))) ;; ALGORITHM ; The algorithm finds all primes between 2 and m. ;; VARIABLE INITIALIZATION ; L = (list 2) ; n = 3 ; PQ empty priority queue with elements of the type (e,d) in NxN sorted after e. ; INVARIANT ; The idea is to let L, n and PQ satisfy these invariants in the main loop. ; 1. n odd ; 2. L = { p | p in [2,n-1] prime } ; 3. eliminated(PQ) = { x in [n,N] | there exists p in [2,n-1] s.t. p|x } ; = { x in [n,N] | there exists (e,d) s.t. d|x-e } ; 4. for all (e,d) in PQ we have e>=n ; Therefore n is a prime, if n is not equal to the first component of ; the least element (e,d) in PQ. ; primes : integer -> (list integer) ; return list of primes in the range 2 to m (define (primes m) (let loop ([n 3] [L (list 2)] [PQ (empty)]) (if (> n m) L (if (or (empty? PQ) (< n (first (find-min PQ)))) ; n is prime (loop (+ n 2) (cons n L) (update (insert (list (* 2 n) n) (* 2 n) PQ ) (+ n 1))) ; n is composite (loop (+ n 2) L (update PQ (+ n 1))))))) ; Update "pushes" the already eliminated elements in order to ; satisfy the fourth invariant (i.e. e>n for all elements (e,d) ) ; Note, that it's possible that several elements need updating. ; update : priority-queue integer -> priority-queue (define (update PQ n) (let* ([min (find-min PQ)] [e (first min)] [d (second min)]) (if (<= e n) (update (insert (list (+ e d) d) (+ e d) (delete-min PQ)) n) PQ))) ; pi : integer -> integer ; return the number of primes less or equal to x (define (pi x) (length (primes x))) ; TEST (for-each (lambda (n) (display (format "The number of primes less than ~a is ~a.\n" n (pi n)))) (list 10 100 1000 10000)) (display (format "The primes less than 1000 is: \n~a\n " (reverse (primes 1000))))