使用递归辅助函数检查质数

Question

我正在尝试使用递归检查数字是否为素数。我被要求使用递归辅助函数，但我不确定应该如何实现它。

我想我知道算法，但我从未尝试在 Racket 中使用递归辅助函数。这是我目前的想法：

看n能不能被i = 2整除
设置i = i + 1
如果i^2 <= n继续。
如果i的值没有均分n，那么它一定是素数。

这是我目前所拥有的...

(define (is_prime n)
  (if (<= n 1)
      #f
      (if (= (modulo n 2) 0)
          #f

)

使用递归辅助函数的好方法是什么？

谢谢！

Answer 1

使用 helper 只是意味着您应该将程序分成更小的部分，并可能将带有额外参数的循环封装在单独的过程中 - 在 Scheme 中，循环经常通过递归调用实现。实现 is_prime 过程的一种（天真的）方法是：

(define (is_prime n)
  (cond ((<= n 1) #f)
        ((= n 2) #t)
        ((= (modulo n 2) 0) #f)
        (else (check 3 n))))

; recursive helper
(define (check i n)
  (cond ((> (* i i) n) #t)
        ((= (modulo n i) 0) #f)
        (else (check (+ i 2) n))))

这个程序有很多种实现方式，也有很多可能的优化；以上应该足以让你开始了。

Answer 2

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

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

我更喜欢这个版本。

使用递归辅助函数检查质数

Check for a prime number using recursive helper function

recursion

scheme

primes

racket

primality-test