0

我正在尝试创建一个程序来构建从 2 到任何数字 n 的素数列表。当然，这需要迭代地完成，但我不完全知道我做错了什么。

(define (list-2-to-n n)
    (define (iter n result)
        (if (= n 0)
            result
        (if (< n 2)
           '()
            (if (= (remainder n 3) 0)
                (list-2-to-n (- n 1))
            (if (even? n)
                (list-2-to-n (- n 1))
                (iter (- n 1) (cons n result)))))))

    (iter n '()))

每当测试用例通过过程时，它总是返回()

4

1 回答 1

1

我做错了什么。

让我们来看看。首先，您的缩进非常具有误导性。它确实应该正确反映代码的结构：

(define (list-2-to-n-0 n)       ; a global function
    (define (iter n result)     ; an internal function
        (if (= n 0)             
            result
            (if (< n 2)                        ; **else**
               '()
                (if (= (remainder n 3) 0)
                    (list-2-to-n (- n 1))
                    (if (even? n)              ; **else**
                        (list-2-to-n (- n 1))
                        (iter (- n 1) (cons n result)))))))
    (iter n '()))

如果没有，至少你应该用一些评论清楚地标记替代条款。

现在，您测试输入的数字是否能被 2 或 3 整除，并以完全相同的方式响应。这两种情况真的应该合二为一。此外，我们可以cond在这里使用而不是这么多嵌套if的 s：

(define (list-2-to-n-1 n)       ; a global function 
    (define (iter n result)     ; an internal function
        (cond
            ((= n 0)  result)
            ((< n 2)  '())
            ((or (= (remainder n 2) 0) (= (remainder n 3) 0))
              (list-2-to-n (- n 1))       ; calling a global function, and
            (else                         ;   returning its result
              (iter (- n 1)               ; calling internal function, and
                    (cons n result)))))   ;   returning its result
    (iter n '()))

在那里调用全局函数意味着重新开始整个过程​​——它将 iter使用(). 对于任何高于 0 的初始值，您所谓的返回结果的情况n==0实际上是无法访问的，因为将首先遇到该情况，并将返回（确切地说是观察到的行为）。nn < 2()

你不应该重新开始，即你应该总是调用内部函数。你应该修复你的基本情况。最后但并非最不重要的一点是，仅检查 2 或 3 的整除性是不够的，已经是 5。所以让我们写isPrime在那里，稍后再实现它：

(define (list-2-to-n-1 n)       ; a global function
    (define (iter n result)     ; an internal function
        (cond
            ((< n 2)  result)
            ((not (isPrime n))
              (iter (- n 1) result))      ; calling internal function, without
            (else                         ;   altering the accumulator
              (iter (- n 1)               ; calling internal function, 
                    (cons n result)))))   ;   altering the accumulator
    (iter n '()))

isPrime需要尝试除以n2,3,... 不需要尝试除以任何高于 2 的偶数，只要赔率就足够了。不需要尝试任何潜在的除数d，d * d > n因为如果n = f * d, f <= d那么f*d <= d*die n <= d*d。

当然，尝试除以 9、15、77 之类的任何复合数也是多余的 - 如果其中任何一个除数，n那么它们的主要因子之一 3、5、7、11 也会除以它，我们会更早地检测到它们。所以实际上，只尝试除以素数就足够了。为了能够做到这一点，您需要重组您的代码，以便它按升序构建其生成的素数列表，并使用其前缀部分不大于sqrt(k)测试每个候选者k。

这被称为试除算法。然后是更快的 Eratosthenes 筛子。

于 2013-10-31T09:08:36.643 回答