计划素数 [英] Scheme prime numbers

问题描述

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

this is possibly much of an elementary question, but I'm having trouble with a procedure I have to write in Scheme. The procedure should return all the prime numbers less or equal to N (N is from input).

(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 ))

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

My check for prime works, however the function printPrimesUpTo seem to loop forever. Basically the idea is to check whether a number is prime and put it in a result list.

谢谢:)

推荐答案

首先，通过缩进来表达嵌套结构是一种很好的风格，所以它视觉上很明显； 并且也把每个if 的子句，consequent 和 alternative，单独一行:

First, it is good style to express nested structure by indentation, so it is visually apparent; and also to put each of if's clauses, the consequent and the alternative, on its own line:

(define (isPrimeHelper x k)
  (if (= x k) 
      #t                           ; consequent
      (if (= (remainder x k) 0)    ; alternative
  ;; ^^ indentation
          #f                               ; consequent
          (isPrimeHelper x (+ k 1)))))     ; alternative

(define (printPrimesUpTo n)
    (define result '())
    (define (helper x)
        (if (= x (+ 1 n)) 
            result                  ; consequent
            (if (isPrime x)         ; alternative
                (cons x result) ))         ; no alternative!
        ;; ^^ indentation
        ( helper (+ x 1)))
    ( helper 1 ))

现在很明显，您的 helper 函数所做的最后一件事是始终使用递增的 x 值调用自身.没有停止条件，即这是一个无限循环.

Now it is plainly seen that the last thing that your helper function does is to call itself with an incremented x value, always. There's no stopping conditions, i.e. this is an infinite loop.

另一件事是，调用 (cons x result) 不会以任何方式改变 result 的值.为此，您需要设置它，如下所示:(set!result (cons x result)).您还需要将此表达式放在 begin 组中，因为它不是根据其值计算的，而是根据它的 副作用:

Another thing is, calling (cons x result) does not alter result's value in any way. For that, you need to set it, like so: (set! result (cons x result)). You also need to put this expression in a begin group, as it is evaluated not for its value, but for its side-effect:

    (define (helper x)
        (if (= x (+ 1 n)) 
            result        
            (begin 
                (if (isPrime x) 
                    (set! result (cons x result)) )   ; no alternative!
                (helper (+ x 1)) )))

通常，显式使用 set! 被认为是不好的风格.表达循环的一种标准方法是使用 named let尾递归代码>，通常使用规范名称loop"(但它可以是任何名称):

Usually, the explicit use of set! is considered bad style. One standard way to express loops is as tail-recursive code using named let, usually with the canonical name "loop" (but it can be any name whatever):

(define (primesUpTo n) 
  (let loop ((x n) 
             (result '())) 
    (cond 
      ((<= x 1) result)      ; return the result
      ((isPrime x) 
            (loop (- x 1) (cons x result)))   ; alter the result being built
      (else (loop (- x 1) result)))))         ; go on with the same result

在存在尾调用优化的情况下，实际上与之前的版本等效.

which, in presence of tail-call optimization, is actually equivalent to the previous version.

这篇关于计划素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！