;;; Fichier eratos.drs / 9 mai 2001

;;; Calcul des nombres premiers inferieurs a n
 
(define (eratos n) (crible1 (cdr (iota n))))
(define (eratos2 n) (crible2 n))
 
(define (crible liste)   ;... algorithme d'Eratosthene
  (cond ((null? liste) ())
        (else (cons (car liste)
                    (crible (filtrer (cdr liste)
                                     (car liste)))))))

(define (filtrer liste d)   ;...enleve les multiples de d
  (cond ((null? liste) ())
        ((= (remainder (car liste) d) 0) 
         (filtrer (cdr liste) d))
        (else (cons (car liste) (filtrer (cdr liste) d)))))

;;; Version terminale

(define (crible1 liste)   ;... algorithme d'Eratosthene
  (define (aux l res)
    (cond ((null? l) (reverse res))
          (else (aux (filtrer1 l (car l)) (cons (car l) res)))))
  (aux liste ()))

(define (filtrer1 liste d)   ;...enleve les multiples de d
  (define (aux l res)
   (cond ((null? l) (reverse res))
         ((= (remainder (car l) d) 0) (aux (cdr l) res))
         (else (aux (cdr l) (cons (car l) res)))))
  (aux liste ()))
        
(define (iota n)   ;... entiers de 1 a n
  (define (aux k res)
    (cond ((> k n) (reverse res))
          (else (aux (+ k 1) (cons k res)))))
  (aux 1 ()))

;;; Optimisation racine(n)

(define (crible2 n)
  (define (aux l res)
    (cond ((or (> (car l) (sqrt n)) 
               (null? l)) (append (reverse res) l))
          (else (aux (filtrer1 l (car l)) (cons (car l) res)))))
  (aux (cdr (iota n)) ()))