0

以下程序找到给定数 n 的最小整数除数（大于 1）。它以一种直接的方式做到这一点，通过测试 n 是否可以被从 2 开始的连续整数整除。

(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))

我们可以如下测试一个数是否为素数：n 是素数当且仅当 n 是它自己的最小除数。

(define (prime? n)
  (= n (smallest-divisor n)))

find-divisor 的最终测试基于这样一个事实，即如果 n 不是素数，则它必须有一个小于或等于 n 的除数。44 这意味着该算法只需要测试 1 和 n 之间的除数。因此，将 n 识别为素数所需的步骤数将具有增长顺序 (n)。

4

1 回答 1

3

您的最后一段被复制时有一些错误。它是sqrt(n)，而不是n，这从阅读代码中显而易见。

要理解这段代码，你需要慢慢地阅读它。这本书的作者专门以这种冗长的方式编写了他们的代码，以便可以用英语慢慢阅读并在阅读时理解它。据我了解，这就是他们的目标。

像这样：

(define (smallest-divisor n)
  (find-divisor n 2))

我们将数字n的最小除数定义为找到n的除数且起始值为2的结果。因此，我们不会将1视为数字的除数。到目前为止，一切都很好。

(define (find-divisor n test-divisor)

找到一个数字n的除数，其起始值为test divisor是通过以下方式完成的（好吧，我们知道我们从2开始；因为它是一个参数，所以这段代码准备好处理给它的任何值......这些是什么values? 现在我们知道2是一种可能性；让我们保持这个想法，稍后再重新检查）：

  (cond ((> (square test-divisor) n) n)

  1. 首先将测试除数的平方与n进行比较，如果平方大于n，则返回n作为结果。我们找到了！

        ((divides? test-divisor n) test-divisor)

  2. 如果之前的测试不成功，我们接下来尝试测试test divisor是否除n。如果是，我们返回测试除数作为结果。我们找到了！

        (else (find-divisor n (+ test-divisor 1)))))

  3. 如果之前的所有测试都失败了，我们就来到了问题的关键：

    • 找到一个数字n的除数，其值为test divisor但没有成功，这与找到一个数字n的除数，其起始值是这个 test divisor 值 加 1是一样的！


    这只是用简单的英语表示，“让我们尝试将n除以下一个测试数字”。

（.. 那么，除了2之外，测试除数可能有哪些值？）

(define (divides? a b)
  (= (remainder b a) 0))

你现在能完成吗？

于 2017-12-16T19:40:36.323 回答