Eratosthenesスキームのふるい

Question

私は、スキームのSag of Eratosthenesの実装をWebで検索していましたが、多くのコンテンツが出てきましたが、完了する必要があるようなものはありませんでした。

ほとんどのアルゴリズムは、静的な終了または反復を使用しています。これは私の言語の知識が不足しているため、皆さんに助けを求めてくれました。

1つの引数（Sieveまでの数値）を取り、再帰のみを使用し、#t（真）または#f（偽）の数値の「短所」のリストを持つSieveの実装が必要です。

だから、基本的なアルゴリズムは、次のような行く：

1. 2からリストを作る - 真
2. を開始する各番号のinputed数が再帰的に通過し、2偽
で割り切れる各番号をマーク唯一の素数をリスト

真

出力をマーク残されるまで

はその後、リスト内の次の「真」の数に上に行きます

出力例：

>（ERAT篩20）

（（2。 #tを） （3。#tを） （4。#fを） （5。#tを） （6。#fを） （7。#tを） （8。#fを） （9＃ F） （10。#fを） （11。#tを） （12。#fを） （13。#tを） （14。#fを） （15。#fを） （16。#fを） （17。#tを） （18。#fを） （19。#tを） （20。は#f））

あなたも徹底的にコードを説明するコメントを持つことができた場合は、それは非常に高く評価されます。

ありがとうございました！

は改訂::: だから私はさらに私の質問を説明するためのスキームを少し学んだ...

を。これは、リストを作ります。

(define (makeList n) 
(if (> n 2) 
    (append (makeList (- n 1)) (list (cons n (and)))) 
    (list (cons 2 (and))))) 

これは、除数の各倍数がfalseになっているリストを返します。

(define (mark-off-multiples numbers divisor) 
(if (null? numbers) 
    '() 
    (append 
    (list (cons (car (car numbers)) 
       (not (zero? (modulo (car (car numbers)) divisor))))) 
    (mark-off-multiples (cdr numbers) divisor)))) 

は今、これは動作するはずのように、私はそれを介して手動で3回行ってきたようで、私はとのトラブルを抱えている機能ですが、その私が必要なものを返さない理由を私は理解できません。関数名が示唆するよう

(define (call-mark-off-multiples-for-each-true-number numbers) 
(if (null? numbers) 
    '() 
    (if (cdr (car numbers)) 
    (append (list (car numbers)) 
      (call-mark-off-multiples-for-each-true-number 
       (mark-off-multiples (cdr numbers) (car (car numbers))))) 
    (append (list (car numbers)) 
      (call-mark-off-multiples-for-each-true-number 
       (cdr numbers)))))) 

である私はそれを行うにしようとしてる、まだダウンリスト真のマークされた各番号のマーク・オフ倍数を呼び出します。したがって、((3.#t)(4.#t)(5.#t))を渡した後、mark-off-multiplesを2に呼び出して(3.#t)(4.#f)(5.#t)を返し、(2.#t)を追加します。そして、それが再び(3.#t)(4.#f)(5.#t)に渡して自分自身を呼び出し、(4.#f)(5.#t)を返すリストのCDRとマーク・オフ倍数を呼び出し、リストを下にいっている...私は、返されます

出力はすべてtruesとリストです。

これはうまくいけば、私の苦境をよく理解するのに役立ちます。

Answer 1

で見つけることができます。

(define (divides? m n) 
    (if (eq? (modulo n m) 0) 
     #t 
     #f)) 

(define (mark-true n) 
    (cons n #t)) 

(define (mark-divisors n ns) 
    (cond ((null? ns) '()) 
     ((and (unmarked? (car ns)) 
       (divides? n (car ns))) 
      (cons (cons (car ns) #f) (mark-divisors n (cdr ns)))) 
     (else (cons (car ns) (mark-divisors n (cdr ns)))))) 

(define (unmarked? n) 
    (not (pair? n))) 

(define (eratosthenes x) 
    (cond ((null? x) '()) 
     ((unmarked? (car x)) 
      (cons (mark-true (car x)) 
       (eratosthenes (mark-divisors (car x) (cdr x))))) 
     (else (cons (car x) (eratosthenes (cdr x)))))) 

(eratosthenes (list 2 3 4 5 6)) 

私は、ヘルパー関数の数を使用してきましたが、あなたが望む場合は、エラトステネスの機能にそれらを追加することができます。私はこのビジネス全体をより読みやすくすると思います。

mark-trueは、#tに値を受け取ります。 mark-divisorsは数字nと数字のリストを取り、nが割り算する数字のすべてを#fに分割します。他のほとんどすべては自明です。エラトステネスは、最初の数字が「マークされていない」場合は「真」または「素数」とマークし、その後、リストの残りからすべての倍数を切り出し、リスト内の数字。私のエラトステネス機能は本質的にあなたがあなたとやりたいことをしています。私はあなたの問題が何であるか分かりませんが、原則として、ヘルパーにあなたの情報をより読みやすくさせることが役立ちます。

私はNeil Van DykeのSICPパッケージでDrRacketでこれを行いました。私はどのスキームを使用しているのか分かりません。あなたがこれを動作させるのに問題がある場合は教えてください。

Answer 2

コードと説明はここで機能するソリューションがあるSICP 3.5.2Infiniteストリーム http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2

Answer 3

OK、SOEのポイントはどの割り切れるをテストすることはありませんが、ただ一度P数字で、数えるので：

(define (make-list n)    ; list of unmarked numbers 2 ... n 
    (let loop ((i n) 
      (a '())) 
    (if (= i 1) 
     a   ; (cons '(2 . #t) (cons (3 . #t) ... (list '(n . #t))...)) 
     (loop (- i 1) (cons (cons i #t) a))))) 

(define (skip2t xs)    ; skip to first unmarked number 
    (if (cdar xs) xs (skip2t (cdr xs)))) 

(define (mark-each! k n i xs)  ; destructive update of list xs - 
    (set-cdr! (car xs) #f)   ; mark each k-th elem, 
    (if (<= (+ i k) n)    ; head is i, last is n 
    (mark-each! k n (+ i k) 
        (list-tail xs k)))) 

(define (erat-sieve n) 
    (let ((r (sqrt n))    ; unmarked multiples start at prime's square 
     (xs (make-list n))) 
    (let loop ((a xs)) 
     (let ((p (caar a)))   ; next prime 
     (cond ((<= p r) 
       (mark-each! p n (* p p) (list-tail a (- (* p p) p))) 
       (loop (skip2t (cdr a))))))) 
    xs)) 

(erat-sieve 20) ==> ((2 . #t) (3 . #t) (4) (5 . #t) (6) (7 . #t) (8) (9) (10) (11 . #t) (12) (13 . #t) (14) (15) (16) (17 . #t) (18) (19 . #t) (20))

---

ようにするには無限大ふるい、式の後に

  P = {3,5,7,9、...} U {{P、P + 2P、P + 4P \ p + 6p、...} | MITスキームでテスト

;;;; Stream Implementation 
(define (head s) (car s)) 
(define (tail s) ((cdr s))) 
(define-syntax s-cons 
    (syntax-rules() ((s-cons h t) (cons h (lambda() t))))) 

;;;; Stream Utility Functions 
(define (from-By x s) 
    (s-cons x (from-By (+ x s) s))) 
(define (take n s) 
    (cond ((= n 0) '()) 
     ((= n 1) (list (car s))) 
     (else (cons (head s) (take (- n 1) (tail s)))))) 
(define (drop n s) 
    (cond ((> n 0) (drop (- n 1) (tail s))) 
     (else s))) 
(define (s-map f s) 
    (s-cons (f (head s)) (s-map f (tail s)))) 
(define (s-diff s1 s2) 
    (let ((h1 (head s1)) (h2 (head s2))) 
    (cond 
    ((< h1 h2) (s-cons h1 (s-diff (tail s1)  s2))) 
    ((< h2 h1)   (s-diff  s1 (tail s2))) 
    (else     (s-diff (tail s1) (tail s2)))))) 
(define (s-union s1 s2) 
    (let ((h1 (head s1)) (h2 (head s2))) 
    (cond 
    ((< h1 h2) (s-cons h1 (s-union (tail s1)  s2))) 
    ((< h2 h1) (s-cons h2 (s-union  s1 (tail s2)))) 
    (else  (s-cons h1 (s-union (tail s1) (tail s2))))))) 

;;;; odd multiples of an odd prime 
(define (mults p) (from-By (* p p) (* 2 p))) 

;;;; The Sieve itself, bounded, ~ O(n^1.4) in n primes produced 
;;;; (unbounded version runs at ~ O(n^2.2), and growing worse) 
;;;; **only valid up to m**, includes composites above it  !!NB!! 
(define (primes-To m) 
    (define (sieve s) 
    (let ((p (head s))) 
    (cond ((> (* p p) m) s) 
     (else (s-cons p 
       (sieve (s-diff (tail s) (mults p)))))))) 
    (s-cons 2 (sieve (from-By 3 2)))) 

;;;; all the primes' multiples, tree-merged, removed; 
;;;; ~O(n^1.17..1.15) time in producing 100K .. 1M primes 
;;;; ~O(1) space (O(pi(sqrt(m))) probably) 
(define (primes-TM) 
    (define (no-mults-From from) 
     (s-diff (from-By from 2) (s-tree-join (s-map mults odd-primes)))) 
    (define odd-primes 
     (s-cons 3 (no-mults-From 5))) 
    (s-cons 2 (no-mults-From 3))) 

;;;; join an ordered stream of streams (here, of primes' multiples) 
;;;; into one ordered stream, via an infinite right-deepening tree 
(define (s-tree-join sts)        ;; sts -> s 
    (define (join-With of-Tail sts)      ;; sts -> s 
    (s-cons (head (head sts)) 
       (s-union (tail (head sts)) (of-Tail (tail sts))))) 
    (define (pairs sts)         ;; sts -> sts 
    (s-cons (join-With head sts) (pairs (tail (tail sts))))) 
    (join-With (lambda (t) (s-tree-join (pairs t))) sts)) 

;;;; Print 10 last primes from the first thousand primes 
(begin 
    (newline) 
    (display (take 10 (drop 990 (primes-To 7919)))) (newline) 
    (display (take 10 (drop 990 (primes-TM)))) (newline)) 

：

はSICPを使用して定義することができる} P にpはストリーム（hereを見ることができるように）スタイル。

Answer 4

(define (prime-sieve-to n) 
    (let* ((sz (quotient n 2)) (sv (make-vector sz 1)) (lm (integer-sqrt n))) 
    (for ((i (in-range 1 lm))) 
     (cond ((vector-ref sv i) 
     (let ((v (+ 1 (* 2 i)))) 
      (for ((i (in-range (+ i (* v (/ (- v 1) 2))) sz v))) 
      (vector-set! sv i 0)))))) 
    (cons 2 
      (for/list ((i (in-range 1 sz)) 
        #:when (and (> (vector-ref sv i) 0) (> i 0))) 
        (+ 1 (* 2 i)))))) 

これは、最大100,000,000まで動作するスキームのラケット方言の別の1つです。その上、私はその効率を保証しません。