Нахождение простого числа в схеме с использованием естественной рекурсии

Question

Я до сих пор работаю над упражнениями «Как разрабатывать программы», но мне снова удалось застрять. На этот раз это вопрос 11.4.7:

Разработка функции это-не-делимой-с <= я. Потребляет натуральное число [> = 1], i и натуральное число м, с я <м. Если м нет делится на любое число от 1 (эксклюзив) и я (включительно), функция производит истину; в противном случае его вывод ложен. </p>

Используйте is-not-divisible-by <= i для определения премьер ?, который потребляет натуральный номер и определяет, стоит ли это просто. </p>

Первая часть, с которой мне не пришлось слишком много времени:

;; A natural number [>=1] is either 1. 1 or 
;; 2. (add1 n) where n is a natural number [>=1].

;; is-not-divisible-by<=i : N[>=1] N -> boolean
(define (is-not-divisible-by<=i i m)
  (cond
    [(= i 1) true]
    [else (cond
            [(= (remainder m i) 0) false]
            [else (is-not-divisible-by<=i (sub1 i) m)])]))
(is-not-divisible-by<=i 3 6) ; expected: false.
(is-not-divisible-by<=i 6 7) ; expected: true.

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

Единственное решение, которое я вижу, - это дать другой переменной - скажем, x - то же значение, что и для n, а затем просто сделать это так, чтобы это не делилось на <= i. Но я думаю, что авторы намерены сделать это другим, более простым способом. (И я даже не знаю, как делать то, что я описал, хаха.) </p>

Эта проблема действительно разрушает мою задницу, так что любая помощь или подсказки, если бы вы могли, были бы великолепны!

Answer 1

Простое число - это число, которое не может быть разделено ни на одно число меньше его самого. Вы уже реализовали часть «не может быть разделена ни на одно число меньше»:

(define (prime? n)
  (is-not-divisible-by<=i (sub1 n) n))

Answer 2

(штрих? 1) получает ошибку «деление на ноль».

- это модифицированная версия исходного кода.Сейчас он решает проблему (простого? 1).

(define (prime? p)
  (define (non-divisible-by n d)
    (cond
     ((= d 1) #t)
     (else (if(= (remainder n d) 0)
          #f
          (non-divisible-by n (- d 1))))))
  (if (= p 1)
      #t
      (non-divisible-by p (- p 1))))

Теперь (простое? 1) возвращает # t

Answer 3

Нет необходимости делить все числа от n-1 до 2, чтобы проверить простоту. Вам нужно только проверить от (этаж (sqrt n)). Таким образом, более быстрый подход (особенно для больших чисел), который также решает проблему с неопределенной (простой? 1):

(define (prime? n)
  (is-not-divisible-by<=i (floor (sqrt n)) n))