用于在 Scheme 中查找素数的改进筛法
Modified Sieve for finding Prime Numbers in Scheme
我正在研究使用埃拉托色尼筛法得出素数列表的解决方案。所以程序应该找到不超过特定数字“n”的素数。我相信我想出了一个不完整的解决方案，但不确定如何从这里开始。
;;;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，它工作正常。
;;;; 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 辅助函数，它工作正常。
我的问题是辅助函数“sievehelper”如何作为除数遍历列表中的不同元素。
感谢任何帮助。谢谢。
导致卡住的一段代码是 (if ( > (car list) (sqrt (car(reverse list))))，它看起来很像您可能在其他语言中使用的循环条件（并且“迭代”一词暗示偷看其他语言，因为嗯）。
我建议您重新开始，采用不同的策略。
当您使用列表时，您通常希望单独递归它们的结构。
假设您有所有整数的列表，从 2 开始。
作为第一步，您想要保留这两个，并从列表的其余部分中删除它的所有倍数。
现在，删除的结果将为您提供一个以下一个素数开头的列表 - 即 3 - 因此您可以使用该部分结果重复该过程，这将删除所有 3 的倍数，并再次重复该部分结果，并且以此类推，直到没有更多列表。
（请注意，这远未达到应有的效率，但更像是“开始递归思考”级别的建议。阅读 Will 的回答了解更多信息。）
应用一些一厢情愿的想法并假设有一个程序 remove-multiples-of 听起来像这样，这可能看起来像这样：
(define (my-sieve-helper ls)
(if (null? ls)
'()
(cons (car ls)
(my-sieve-helper (remove-multiples-of (car ls) (cdr ls))))))
所以，remove-multiples-of...
这与保留所有不能被数字整除的数字是一样的，所以让我们想象另一个函数：
(define (remove-multiples-of x ls) (filter (not-divisible-by x) ls))
其中 (not-divisible-by x) 是一个过程，它接受一个数字和 returns 该数字是否不能被 x 整除。
(define (not-divisible-by n) (lambda (x) (not (zero? (remainder x n)))))
现在我们可以添加合适的包装器了。
我这样做了：
(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)
好吧，您的问题提出了一个有趣的规格不足的案例，这可能是有利的，延迟实际的规格 -- 不仅仅是像往常一样实现 -- 您的代码使用的子例程。
这里我们有 sievehelper，它使用未实现的未指定的 filterfunc 和 not-divisible-by。尽管它们的名称具有暗示性，但只要它们一起使用并使使用它们的函数 sievehelper 也能按预期工作，只要它们能正常工作，它们就可以做任何事情。 Delayed specification for the win!
那么让我们首先看看给定的 sievehelper 有什么用，它有什么作用？假设这两个子程序的含义很明显，它似乎打算对其工作序列执行一步过滤，从其“head”元素的任何倍数中剔除它，即位于 car 位置的元素。
它将通过返回 () 来表示停止条件。对于 [a,b,c,...,z].
的输入列表，停止条件是 a*a > z
否则不执行循环，只执行其中的一步。您的 sieve 根本没有考虑到这一点，因此需要更改为不断调用此帮助程序，像通常在筛选算法中一样一步一步地执行，直到第一个元素的平方大于最后一个工作序列中的元素，当停止剔除确实安全时，因为序列中的所有倍数都已经作为较小素数的倍数从中删除......提供那些较小的素数存在于初始序列中。
所以这个发现的需求落在了第三个未实现的正在使用的子路由上，makelist。您确实提到它必须创建从 2 到 n 的连续自然数列表，现在我们明白了 为什么 我们需要它这样做。
那么，为了迭代 through输入列表的不同版本，因为每个除数依次从中过滤掉，使用您的 sievehelper 定义 给定 ，您的 sieve 函数必须更改为例如
(define sieve
(lambda (n)
(let ((init (makelist n)))
(let loop ((this init )
(next (sievehelper init)))
(if (null? next)
this
(cons (car this)
(loop next
(sievehelper next))))))))
（上面的代码合并了 by ad-absurdum from the followup ，到这个代码原来包含的错误）。
这段代码是从处理对——当前序列及其下一个迭代的角度出发的。在每个步骤中，在其 head 元素的所有倍数被 sievehelper 从列表中删除之后找到列表的下一个版本（包括 head 元素本身，下一个找到的素数) -- 或者当 all 已知列表中的数字已经是素数时返回空列表以表示处理结束，通过构造.
在 Racket 中试用：
> (sieve 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)
要运行它，必须进一步定义：
(define filterfunc filter)
(define (not-divisible-by n) ; NB! this critically depends on
(let ((m n)) ; filterfunc working over its
(lambda (x) ; argument list _in order_ NB!
(let ((ret (not (= x m))))
(if (>= x m) (set! m (+ m n)) #f)
ret))))
(define (makelist n)
(range 2 (+ 1 n))) ; in Racket
像我们在这里所做的那样定义 not-divisible-by，通过迭代加法在内部枚举每个素数的倍数，使其确实成为 Eratosthenes 的筛子。并提前停止（在限制的平方根处），就像在您的原始代码中一样，将其时间复杂度保持在理智的一面，更接近最佳。
我正在研究使用埃拉托色尼筛法得出素数列表的解决方案。所以程序应该找到不超过特定数字“n”的素数。我相信我想出了一个不完整的解决方案，但不确定如何从这里开始。
;;;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，它工作正常。
;;;; 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 辅助函数，它工作正常。
我的问题是辅助函数“sievehelper”如何作为除数遍历列表中的不同元素。
感谢任何帮助。谢谢。
导致卡住的一段代码是 (if ( > (car list) (sqrt (car(reverse list))))，它看起来很像您可能在其他语言中使用的循环条件（并且“迭代”一词暗示偷看其他语言，因为嗯）。
我建议您重新开始，采用不同的策略。
当您使用列表时，您通常希望单独递归它们的结构。
假设您有所有整数的列表，从 2 开始。
作为第一步，您想要保留这两个，并从列表的其余部分中删除它的所有倍数。
现在，删除的结果将为您提供一个以下一个素数开头的列表 - 即 3 - 因此您可以使用该部分结果重复该过程，这将删除所有 3 的倍数，并再次重复该部分结果，并且以此类推，直到没有更多列表。
（请注意，这远未达到应有的效率，但更像是“开始递归思考”级别的建议。阅读 Will 的回答了解更多信息。）
应用一些一厢情愿的想法并假设有一个程序 remove-multiples-of 听起来像这样，这可能看起来像这样：
(define (my-sieve-helper ls)
(if (null? ls)
'()
(cons (car ls)
(my-sieve-helper (remove-multiples-of (car ls) (cdr ls))))))
所以，remove-multiples-of...
这与保留所有不能被数字整除的数字是一样的，所以让我们想象另一个函数：
(define (remove-multiples-of x ls) (filter (not-divisible-by x) ls))
其中 (not-divisible-by x) 是一个过程，它接受一个数字和 returns 该数字是否不能被 x 整除。
(define (not-divisible-by n) (lambda (x) (not (zero? (remainder x n)))))
现在我们可以添加合适的包装器了。
我这样做了：
(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)
好吧，您的问题提出了一个有趣的规格不足的案例，这可能是有利的，延迟实际的规格 -- 不仅仅是像往常一样实现 -- 您的代码使用的子例程。
这里我们有 sievehelper，它使用未实现的未指定的 filterfunc 和 not-divisible-by。尽管它们的名称具有暗示性，但只要它们一起使用并使使用它们的函数 sievehelper 也能按预期工作，只要它们能正常工作，它们就可以做任何事情。 Delayed specification for the win!
那么让我们首先看看给定的 sievehelper 有什么用，它有什么作用？假设这两个子程序的含义很明显，它似乎打算对其工作序列执行一步过滤，从其“head”元素的任何倍数中剔除它，即位于 car 位置的元素。
它将通过返回 () 来表示停止条件。对于 [a,b,c,...,z].
a*a > z
否则不执行循环，只执行其中的一步。您的 sieve 根本没有考虑到这一点，因此需要更改为不断调用此帮助程序，像通常在筛选算法中一样一步一步地执行，直到第一个元素的平方大于最后一个工作序列中的元素，当停止剔除确实安全时，因为序列中的所有倍数都已经作为较小素数的倍数从中删除......提供那些较小的素数存在于初始序列中。
所以这个发现的需求落在了第三个未实现的正在使用的子路由上，makelist。您确实提到它必须创建从 2 到 n 的连续自然数列表，现在我们明白了 为什么 我们需要它这样做。
那么，为了迭代 through输入列表的不同版本，因为每个除数依次从中过滤掉，使用您的 sievehelper 定义 给定 ，您的 sieve 函数必须更改为例如
(define sieve
(lambda (n)
(let ((init (makelist n)))
(let loop ((this init )
(next (sievehelper init)))
(if (null? next)
this
(cons (car this)
(loop next
(sievehelper next))))))))
（上面的代码合并了
这段代码是从处理对——当前序列及其下一个迭代的角度出发的。在每个步骤中，在其 head 元素的所有倍数被 sievehelper 从列表中删除之后找到列表的下一个版本（包括 head 元素本身，下一个找到的素数) -- 或者当 all 已知列表中的数字已经是素数时返回空列表以表示处理结束，通过构造.
在 Racket 中试用：
> (sieve 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)
要运行它，必须进一步定义：
(define filterfunc filter)
(define (not-divisible-by n) ; NB! this critically depends on
(let ((m n)) ; filterfunc working over its
(lambda (x) ; argument list _in order_ NB!
(let ((ret (not (= x m))))
(if (>= x m) (set! m (+ m n)) #f)
ret))))
(define (makelist n)
(range 2 (+ 1 n))) ; in Racket
像我们在这里所做的那样定义 not-divisible-by，通过迭代加法在内部枚举每个素数的倍数，使其确实成为 Eratosthenes 的筛子。并提前停止（在限制的平方根处），就像在您的原始代码中一样，将其时间复杂度保持在理智的一面，更接近最佳。