埃拉托色尼筛法 [英] Sieve of Eratosthenes Scheme

问题描述

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

I've been searching the web for an implementation of the Sieve of Eratosthenes in scheme and although I came up with a lot of content, none of them seemed to have made it like I need it to be done.

问题是大多数算法要么使用静态端，要么使用迭代.再加上我缺乏语言知识，我向大家寻求帮助.

The problem is most algorithms either use a static end or use iteration. This paired with my lack of knowledge of the language led me to ask all of you for help.

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

I need an implementation of the Sieve that takes in one argument (number to Sieve until), uses only recursion and has a list of "cons" of a number with a #t (true) or #f (false).

所以基本上算法会这样:

So essentially the algorithm would go as such:

1. 从 2 生成列表 - 输入的数字，每个数字都以 true 开头
2. 递归遍历并标记每个可被 2 整除的数字为 false
3. 然后继续查找列表中的下一个真"数，直到只剩下素数标记为真
4. 输出列表

示例输出:

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

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

如果您还可以对代码进行全面解释，我们将不胜感激.

If you could also have comments thoroughly explaining the code, that would be extremely appreciated.

谢谢！

修订版:::所以我学到了一些方案来进一步解释我的问题......

REVISED::: So I've learned a bit of scheme to further explain my question...

这就是列表.

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

这将返回一个列表，其中每个除数的倍数都标记为 false.

This returns a list with each multiple of the divisor marked 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 次，但我不明白为什么它没有返回我需要的内容.

Now this is the function I'm having trouble with, it seems like it should work, I've gone through it manually three times, but I can't figure out why its not returning what I need.

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

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

What I'm trying to make it do is, as the function name suggests, call mark-off-multiples for each number that is still marked true down the list. So you pass in ((3.#t)(4.#t)(5.#t)) and then it calls mark-off-multiples for 2 and returns (3.#t)(4.#f)(5.#t) and you append (2.#t) to it. Then it calls itself again passing in (3.#t)(4.#f)(5.#t) and calls mark-off-multiples with the cdr of the list returning (4.#f)(5.#t) and keeps going down the list...

然后我得到的输出是一个包含所有真值的列表.

The output I then get returned is a list with all trues.

这个，希望能帮助你更好地理解我的困境.

This, hopefully with help you better understand my predicament.

推荐答案

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

Here is a solution that works.

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

我使用了许多辅助函数，但如果您愿意，可以将它们添加到埃拉托色尼函数中.我认为这使整个业务更具可读性.

I've used a number of helper functions, but you could add them to the eratosthenes function if you wanted. I think it makes this whole business more readable.

mark-true 将值转换为 #t.mark-divisors 接受一个数字 n 和一个数字列表，并将 n 划分成一个 #f.几乎所有其他内容都是不言自明的.Eratosthenes 正常工作，如果第一个数字是未标记的"，它会将其标记为真"或素数"，然后从列表的其余部分划掉"它的所有倍数，然后对每个后续的未标记"重复列表中的数字.我的 Eratosthenes 功能基本上可以完成您尝试使用的功能.我不确定你的问题是什么，但作为一项规则，让助手让你的东西更具可读性是有帮助的.

mark-true conses a value onto a #t. mark-divisors takes a number n and a list of numbers and conses all of the numbers that n divides onto a #f. Pretty much everything else is self explanatory. Eratosthenes works as it should, if the first digit is "unmarked" it marks it as "true" or "prime" and then "crosses out" all of its multiples from the remainder of the list and then repeats for each subsequent "unmarked" digit in the list. My eratosthenes function does essentially what you were trying to do with yours. I'm not sure what the problem with yours is, but as a rule, it's helpful to make helpers to make your stuff more readable.

我在 DrRacket 中使用 Neil Van Dyke 的 SICP 包完成了这项工作.不知道你用的是什么Scheme.如果您在使用它时遇到问题，请告诉我.

I did this in DrRacket with Neil Van Dyke's SICP package. I don't know what Scheme you're using. Let me know if you have problems getting this to work.

这篇关于埃拉托色尼筛法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！