3

我一直在网上搜索埃拉托色尼筛法的实施方案，虽然我想出了很多内容，但似乎没有一个能像我需要的那样完成。

问题是大多数算法要么使用静态结束，要么使用迭代。这与我缺乏语言知识相结合，导致我向你们所有人寻求帮助。

我需要一个 Sieve 的实现，它接受一个参数（直到 Sieve 的数字），只使用递归，并且有一个带有#t（真）或#f（假）的数字的“缺点”列表。

所以基本上算法会这样：

  1. 从 2 个输入的数字创建列表，每个数字都以 true 开头
  2. 递归遍历并标记每个可被 2 整除的数字 false
  3. 然后继续到列表中的下一个“真”数字，直到只有素数被标记为真
  4. 输出列表

示例输出：

> (erat-sieve 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))))))

正如函数名称所暗示的那样，我要做的是，为列表中仍然标记为真的每个数字调用 mark-off-multiples。所以你传入，((3.#t)(4.#t)(5.#t))然后它调用mark-off-multiples2 并返回(3.#t)(4.#f)(5.#t)并附(2.#t)加到它。然后它再次调用自己传入(3.#t)(4.#f)(5.#t)并调用 mark-off-multiples 并返回列表的cdr(4.#f)(5.#t)并继续沿着列表向下...

然后我返回的输出是一个包含所有真值的列表。

这一点，希望能帮助你更好地理解我的困境。

4

4 回答 4

2

这是一个有效的解决方案。

(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))

我使用了许多辅助函数，但如果你愿意，可以将它们添加到eratosthenes 函数中。我认为它使整个业务更具可读性。

mark-true将一个值转换为 a #t。mark-divisors接受一个数字n和一个数字列表，并将所有n除以 a的数字组成#f。几乎所有其他内容都是不言自明的。埃拉托色尼按它应该的方式工作，如果第一个数字是“未标记的”，它会将其标记为“真”或“素数”，然后从列表的其余部分“划掉”它的所有倍数，然后对每个后续的“未标记”重复列表中的数字。我的eratosthenes 函数基本上完成了你试图用你的函数做的事情。我不确定你的问题是什么，但作为一项规则，让助手让你的东西更具可读性是有帮助的。

我在 DrRacket 中使用 Neil Van Dyke 的 SICP 包做到了这一点。不知道你用的是什么方案。让我知道您是否在使其正常工作时遇到问题。

于 2012-03-30T04:42:12.260 回答
1

好的，所以 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 2 , p 2 +2p , p 2 +4p , p 2 +6p , ...} | p中的p }

可以使用 SICP 风格的流定义（可以在这里看到）：

 ;;;; 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))

在 MIT 计划中测试。

于 2012-08-24T14:43:37.050 回答
1 
(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。除此之外，我不会保证它的效率。

于 2013-05-18T22:09:22.067 回答
0

代码和解释可以在 SICP 3.5.2Infinite Streams http://mitpress.mit.edu/sicp/full-text/book/book-ZH-24.html#%_sec_3.5.2中找到

于 2012-03-29T07:21:00.477 回答