examples/priority-queue--primes.scm
;;; 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))))