プログラムに計算式とかせるのが好き3 エラトステネスの篩

昨日の素因数分解、

(prime-decomposition (+ (* 2 3 5 7 11 13 17 19 23 29 31) 1))

↑こんな式食わすと帰って来なくなる。ちなみに(+ (* 2 3 5 7 11 13 17 19 23 29 31) 1)=>200560490131
まあそりゃあそうだろ、と思いながら素数のリストが欲しくなって、

エラトステネスの篩

を見て、がんばって書いてみる。

;;インクリメント
(define (1+ n)
  (+ 1 n))

;;(func first)したものをリストにして返す。endと同値になるまで繰り返す
(define (list-iter first end func)
  (let ((return first))
	(if (= return end)
		(list end)
		(cons first (list-iter (func first) end func)))))
;;(list-iter 0 3 1+)=>(0 1 2 3)

;;関数fとリストlを受け取り、fが真を返すもののリストを返す
(define (filter f l)
  (if (equal? l ())								;;リストが空だったら終わり
	  ()
	  (if (f (car l))							;;関数をリストの先頭要素に適用して、
		  (cons (car l) (filter f (cdr l)))		;;真だったらリストの先頭要素と残りの要素をフィルタしてconsして返す
		  (filter f (cdr l)))))					;;偽だったら残りの要素をフィルタして返す

;;エラトステネスの篩
;;2~xまでの素数のリストを返す
(define (Eratosthenes x)
  ;; リストlのうち、nで割り切れない数だけをリストにして返す
  (define (not-dividable-n-filter l n)
	(filter (lambda (x)(not (= 0 (modulo x n)))) l))
  (define (Eratosthenes-iter search-list prime-list)
	(if (null? search-list)prime-list
		(let ((first-prime (car search-list)))
		  (Eratosthenes-iter (not-dividable-n-filter search-list first-prime) (append prime-list (list first-prime))))))
	(Eratosthenes-iter (list-iter 2 x 1+) '()))