#| Для этого упражнения нет проверок.
Любое решение будет считаться успешным ответом. |#
; Необходимые процедуры
; !Важное уточнение! В связи с низкой точностью возвращаемого результата у runtime в реализации LISP'а от MIT, для получения видимого результата будет повторение 1000 раз. Изменена процедура start-prime-test

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime) 10))

(define (start-prime-test n start-time times)
  (define (loop i k)
    (if (= i k)
        (report-prime (- (runtime) start-time))
        (begin
          (fast-prime? n times)
          (loop (+ i 1) k))))
  (if (fast-prime? n times)
      (loop 1 1000)
      #f))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

; Так как у теста Ферма порядок роста O(log n), то ожидаемое соотношение времени между проверкой на простоту поблизости от 1 000 000 и поблизости от 1000 будет (log 1000000) / (log 1000)
; По свойству логарифмов (log b) / (log a) = log_a(b), т. е. (log 1000000) / (log 1000) = log_1000(1000000) = 2
; Ожидаемое соотношение - 2

(timed-prime-test 1009) ; 1009 *** .26999999999999996
(timed-prime-test 1013) ; 1013 *** .3
(timed-prime-test 1019) ; 1019 *** .30000000000000004
; Среднее: 0.29

(timed-prime-test 10007) ; 10007 *** .32999999999999996
(timed-prime-test 10009) ; 10009 *** .33000000000000007
(timed-prime-test 10037) ; 10037 *** .31999999999999984
; Среднее: 0.32(6)

(timed-prime-test 100003) ; 100003 *** .3500000000000003
(timed-prime-test 100019) ; 100019 *** .3799999999999999
(timed-prime-test 100043) ; 100043 *** .3799999999999999
; Среднее: 0.37

(timed-prime-test 1000003) ; 1000003 *** .4200000000000004
(timed-prime-test 1000033) ; 1000033 *** .4299999999999997
(timed-prime-test 1000037) ; 1000037 *** .43999999999999995
(newline)
; Среднее: 0.43

; Отношение: 0.43 / 0.29 = 1.4828...
; Получившиеся данные не подтверждают наше предположение о соотношении. Это связано с особенностями самой процедуры runtime, "костылем" в 1000 запусков и, как следствие, лишние действия между самими операциями