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

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

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

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

Answer 2

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

Существует много способов реализации этой процедуры и множество возможных оптимизаций; вышесказанного должно быть достаточно для начала.