Проверьте простое число, используя рекурсивную вспомогательную функцию

Question

Я пытаюсь проверить, является ли число простым с использованием рекурсии. Мне нужно было использовать рекурсивную вспомогательную функцию, но я не уверен, как мне это реализовать.

Я думаю, что знаю алгоритм, но я никогда не пытался использовать рекурсивную вспомогательную функцию в Racket. Это мои нынешние мысли:

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

)

Что было бы хорошим подходом с использованием рекурсивной вспомогательной функции??

Спасибо!

Answer 1

Использование помощника просто означает, что вы должны разбить вашу программу на более мелкие части и, возможно, инкапсулировать циклы с дополнительными параметрами в отдельных процедурах - и в схемах циклы часто реализуются через рекурсивные вызовы. Один (наивный) способ реализации 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 ) )))

Я предпочитаю эту версию.