方案素数

Question

这可能是一个基本问题，但我在必须用Scheme 编写的过程时遇到了麻烦。该过程应返回所有小于或等于 N 的素数(N 来自输入)。

(define (isPrimeHelper x k)
  (if (= x k) #t
  (if (= (remainder x k) 0) #f
      (isPrimeHelper x (+ k 1)))))

(define ( isPrime x )
    (cond
      (( = x 1 ) #t)
      (( = x 2 ) #t)
      ( else (isPrimeHelper x 2 ) )))

(define (printPrimesUpTo n)
    (define result '())
    (define (helper x)
        (if (= x (+ 1 n)) result
        (if (isPrime x) (cons x result) ))
        ( helper (+ x 1)))
    ( helper 1 ))

我对 prime 的检查有效，但是函数 printPrimesUpTo 似乎永远循环。基本上，这个想法是检查一个数字是否是质数并将其放入结果列表中。

谢谢:)

Answer 1

您有几处错误，并且您的代码非常不惯用。首先，数字1不是质数；事实上，它既不是素数也不是合数。其次，result 变量没有按照您想象的那样执行。第三，您对 if 的使用在所有出现的地方都是不正确的； if 是一个表达式，而不是像其他一些编程语言中的语句。而且，作为一种风格问题，右括号堆叠在行尾，并且不占用自己的一行。您需要与您的教授或助教交谈，以消除对Scheme的一些基本误解。

找到小于n的素数的最佳算法是埃拉托斯特尼筛法，它是由一位希腊数学家在大约二十二世纪前发明的，他发明了闰日和纬度和经度系统，准确测量了地球的周长和地球到太阳的距离，并且是亚历山大托勒密图书馆的首席图书管理员。这是他的算法的简单版本:

(define (primes n)
  (let ((bits (make-vector (+ n 1) #t)))
    (let loop ((p 2) (ps '()))
      (cond ((< n p) (reverse ps))
            ((vector-ref bits p)
              (do ((i (+ p p) (+ i p))) ((< n i))
                (vector-set! bits i #f))
              (loop (+ p 1) (cons p ps)))
            (else (loop (+ p 1) ps))))))

调用为(primes 50)，返回列表(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)。它比您尝试做的通过试除法测试数字素数要快得多。如果您必须，这里是一个合适的素性检查器:

(define (prime? n)
  (let loop ((d 2))
    (cond ((< n (* d d)) #t)
          ((zero? (modulo n d)) #f)
          (else (loop (+ d 1))))))

这两种算法都可以改进。如果你有兴趣，我谦虚地推荐这个essay在我的博客上。