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

问题描述 投票:2回答:2

我想,以检查是否使用递归的数是素数。我需要使用递归辅助函数,但我不知道我应该如何实现它。

我想我知道的算法,但我从来没有尝试过的球拍使用递归辅助函数。这是我目前的想法:

  1. 见若n整除i = 2
  2. 设置i = i + 1
  3. 如果i^2 <= n继续。
  4. 如果没有i值平分秋色n,那么它必须是素数。

这是我迄今为止...

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

)

什么是使用递归辅助函数的好办法?

谢谢!

recursion scheme racket primes primality-test
2个回答
4
投票

使用辅助仅仅意味着你应该在更小的部分分割你的程序,并可能封装在单独的程序额外的参数的循环 - 在循环方案通过递归调用频繁执行。一(天真)的方式来实施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))))

有实现这个过程中,许多可能的优化方法很多;以上应该足够让你开始。


0
投票
(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 ) )))

我喜欢这个版本。

© www.soinside.com 2019 - 2024. All rights reserved.