用于在 Scheme 中查找素数的修改筛 [英] Modified Sieve for finding Prime Numbers in Scheme

问题描述

我正在研究使用埃拉托色尼筛法提供素数列表的解决方案.因此该程序应该找到直到特定数字n"的素数.我相信我想出了一个不完整的解决方案，但不知道如何从这里开始.

I am working on coming up with a solution for coming with a list of prime numbers using the Sieve of Eratosthenes. So the program is supposed to find prime numbers up to a specific number "n". I believe I have come up with an incomplete solution but not sure how to proceed from here.

;;;This is a helper function
(define sievehelper 
   (lambda (list)
      ;;; This is the base condition where we are comparing 
      ;;; that the divisor is less than the square root of n""
      (if (> (car list) (sqrt (car (reverse list))))
          '()
          ;;; If the base condition has not be reached, then send it through 
          ;;; this filter function where not-divisible by will go through
          ;;; the specified list and only output the list which contains
          ;;; the numbers that are not divisible by (car list)
          (filterfunc (not-divisible-by (car list)) 
                      list)))

我已经单独测试了另一个辅助函数 fliterfunc 并且它工作正常.

I have tested the other helper function fliterfunc on its own and it works fine.

;;;; This is the main function that calls the above helper function
(define sieve 
   (lambda (n)
      ;;; `makelist` is a helper function to generate the list from 2 to n
      (sievehelper (makelist n))))

我已经单独测试了 makelist 辅助函数，它工作正常.

I have tested the makelist helper function separately and it works fine.

我的问题是关于辅助函数sievehelper"；在如何迭代列表中的不同元素作为除数方面.

My question is with the helper function "sievehelper" in terms of how to iterate through the different elements in the list as the divisor.

感谢任何帮助.谢谢.

推荐答案

导致卡死的一段代码是(if ( > (car list) (sqrt (car(reverse list))))，它看起来很像你可能在其他语言中使用的循环条件(迭代"这个词也暗示了窥视其他语言).
我建议您重新开始，采用不同的策略.

One piece of code that leads to getting stuck is (if ( > (car list) (sqrt (car(reverse list)))), which looks a lot like the loop condition you might use in other languages (and the word "iterate" hints at peeking at other languages, as well).
I would recommend that you start over, with a different strategy.

当您使用列表时，您通常只想递归它们的结构.

When you work with lists, you usually want to recurse on their structure alone.

假设您有所有整数的列表，从 2 开始.
作为第一步，您希望保留这两个，并从列表的其余部分中删除其所有倍数.
现在，删除的结果将为您提供一个以下一个素数(即 3)开头的列表，因此您可以使用该部分结果重复该过程，这将删除 3 的所有倍数，并再次重复该部分结果，并且依此类推，直到没有更多列表.

Assume that you have the list of all integers, starting with 2.
As a first step, you want to keep the two, and remove all its multiples from the remainder of the list.
Now, the result of that removal will give you a list that starts with the next prime number - i.e. 3 - so you can repeat the procedure with that partial result which will remove all multiples of 3, and repeat again with that partial result, and so on until there is no more list.

(请注意，这远没有达到应有的效率，而是更像是开始递归思考"级别的建议.阅读 Will 的答案以了解更多信息.)

(Note that this is far from as efficient as it could be, but is more a "get started with thinking recursively" level of suggestion. Read Will's answer for more.)

应用一些一厢情愿的想法，并假设有一个过程 remove-multiples-of 听起来像这样，这可能看起来像这样:

Applying some wishful thinking and assuming that there is a procedure remove-multiples-of which does what it sounds like, this could look like this:

(define (my-sieve-helper ls)
  (if (null? ls)
      '()
      (cons (car ls)
            (my-sieve-helper (remove-multiples-of (car ls) (cdr ls))))))

所以，删除多个...
这与保留所有不能被数字整除的数字相同，所以让我们想象另一个函数:

So, remove-multiples-of...
This is the same as keeping all the numbers that are not divisible by a number, so let's dream up another function:

(define (remove-multiples-of x ls) (filter (not-divisible-by x) ls))

其中 (not-divisible-by x) 是一个过程，它接受一个数字并返回该数字是否不能被 x 整除.

where (not-divisible-by x) is a procedure that takes a number and returns whether that number is not divisible by x.

(define (not-divisible-by n) (lambda (x) (not (zero? (remainder x n)))))

现在我们可以添加一个合适的包装器.
我是这样做的:

And now we can add a suitable wrapper.
I did this:

(define (from-to m n)
  (if (> m n)
      '()
      (cons m (from-to (+ m 1) n))))

(define (my-sieve n) (my-sieve-helper (from-to 2 n)))

测试:

> (my-sieve 100)
'(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)

这篇关于用于在 Scheme 中查找素数的修改筛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！