In quanti modi riusciamo a scrivere il crivello di Eratostene?

[Gianluca Moro]

ciao,


$ cat eratostene4.scm
;
; Crivello di Eratostene - by giammy - www.giammy.com - giangiammy@gmail.com


; Crivello di eratostene:
;
; L'idea base e' implementata nella funzione genera-successivo e ciclo.
;
; Essenzialmente, posso implementare una pipe line di processi, del tipo
;
; Processo 1: produci il numero successivo (n->n+1)
; Processo 2: prendi il numero prodotto da processo 1, se e' multiplo di 2
;             eliminalo, altrimenti e' il prossimo numero primo
; Processo 3: prendi il numero prodotto da processo 2, se e' multiplo di 3
;             eliminalo, altrimenti e' il prossimo numero primo
;
; Il trucco sta nel fatto che ogni volta che trovo un numero primo,
; devo allungare la pipe di un processo.
; Questo viene fatto nella funzione ciclo
;  ...
;    (ciclo (lambda (n) (genera-successivo indice succ n)) (succ indice))))
;  ...
; in cui ciclo viene chiamata ricorsivamente, aggiornando la funzione
; genera-successivo.
;



; Test RUN:
;
;bash-3.2$ scheme -load eratostene4.scm
;MIT/GNU Scheme running under MacOSX
;Type `^C' (control-C) followed by `H' to obtain information about interrupts.
;
;Copyright (C) 2010 Massachusetts Institute of Technology
;This is free software; see the source for copying conditions. There is NO
;warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
;
;Image saved on Thursday October 28, 2010 at 12:06:49 PM
;  Release 9.0.1 || Microcode 15.1 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
;  Edwin 3.116
;
;2
;3
;5
;7
;11
;13
;17
;19
;23
;29
;31
;37
;41
;43
;47
;53
;59
;61
;67
;71
;73
;79
;83
;89
;97
;101
;103
;107
;109
;113
;127
; ... e via cosi' ...



;
; x e' multiplo di n? ritorna vero o falso
;
(define (multiplo-di? n x)
  (= (* (floor (/ x n)) n) x)
)

;
; successivo: genera il numero naturale successivo
;
(define (successivo n)
  (+ n 1))

;
; prende il prossimo numero non multiplo di base prodotto dal
; precedente generatore
;
(define (genera-successivo base succ indice)
  (let ((prossimo-indice (succ indice)))
    (if (multiplo-di? base prossimo-indice)
	(genera-successivo base succ prossimo-indice)
	prossimo-indice)))

;
; ciclo principale
;
(define (ciclo succ indice)
  (begin
    (display indice)
    (newline)
    (ciclo (lambda (n) (genera-successivo indice succ n)) (succ indice))))

;
; per lanciare il crivello (ATTENZIONE: IL PROGRAMMA NON TERMINA!)
;
(ciclo successivo 2)



-- 
Gianluca Moro --- Enjoy CloudUSB:  http://www.cloudusb.net/
http://www.giammy.com --- http://www.math.unipd.it/~giammy/
Diaspora Forum: http://diasporadoc.info/forum/
Just remember, there's a right way and a wrong way to do everything
and the wrong way is to keep trying to make everybody else do it the
right way