使用自然递归在Scheme中查找素数

我仍然在自己设计程序的练习中插入，但又设法再次卡住了。这一次，它的问题11.4.7：使用自然递归在Scheme中查找素数

的是 - 不除尽，<开发功能 =我。它消耗了自然数[> = 1] i和自然数，其中i为< m。如果m不是可被1 （不包括）和i（包括）之间的任何数字整除，则函数会生成true;否则，其输出是错误的。

使用是-未除尽-由< = i到限定素？，这消耗了自然数和确定是否不它是素数。

我没有太多苦时间第一部分：

;; A natural number [>=1] is either 1. 1 or 
;; 2. (add1 n) where n is a natural number [>=1]. 

;; is-not-divisible-by<=i : N[>=1] N -> boolean 
(define (is-not-divisible-by<=i i m) 
    (cond 
    [(= i 1) true] 
    [else (cond 
      [(= (remainder m i) 0) false] 
      [else (is-not-divisible-by<=i (sub1 i) m)])])) 
(is-not-divisible-by<=i 3 6) ; expected: false. 
(is-not-divisible-by<=i 6 7) ; expected: true.

但我只是不明白我怎么可以使用一个变量，而使用天然递归来做到这一点。我想过使用一个列表，但是也出现了相同的问题。

我能看到的唯一解决办法是给出另一个变量 - 让我们假设x--与n相同的值，然后按照这种方式是不可分割的 - < =我这样做。但我认为作者打算让我以其他更简单的方式做到这一点。（而且我甚至不知道该怎么做我所描述的东西，哈哈。）

这个问题确实是在破坏我的屁股，所以如果可以的话，任何帮助或提示都会很棒！

来源

2010-07-27 James Callaway

素数是一个数字，不能被小于自身的任何数字除。您已经实施了“不能被任何小于”的部分：

(define (prime? n) 
    (is-not-divisible-by<=i (sub1 n) n))

来源

2010-07-27 16:29:10

哦，jeeze，这很尴尬。我认为，如果我这样做了，那么每次函数被递归调用时，两个n的值都会继续下降1。我不认为（sub1 n）会被当作一个x来处理，但是作为一个n，它根本没有什么意义。非常感谢！ – 2010-07-27 16:33:41

这完全取决于你是否按照数值（不能改变）或变量（可以改变）来考虑...... http://www.nicollet.net/2010/01/quick-test/;） – 2010-07-27 16:39:06

（prime？1）得到“除零”的错误。

这里是原始代码的修改版本。它现在需要处理（首要？1）问题。

(define (prime? p) 
    (define (non-divisible-by n d) 
    (cond 
    ((= d 1) #t) 
    (else (if(= (remainder n d) 0) 
      #f 
      (non-divisible-by n (- d 1)))))) 
    (if (= p 1) 
     #t 
     (non-divisible-by p (- p 1))))

现在（质数？1）返回#T

来源

2011-06-23 17:26:11 joe

请注意，如果是1，您应该返回'＃f'，因为1不是素数。 – blubberdiblub 2017-04-23 09:34:37

这不是必要的，你把所有的数字从正1至2检查素性。你只需要从（floor（sqrt n））中检查。所以一个更快的aproach（特别是大数字），也需要关心未定义（prime？1）问题，是：

(define (prime? n) 
    (is-not-divisible-by<=i (floor (sqrt n)) n))

来源

2013-03-16 16:13:23

使用自然递归在Scheme中查找素数

回答

相关问题