;; Die ersten drei Zeilen dieser Datei wurden von DrRacket eingefügt. Sie enthalten Metadaten
;; über die Sprachebene dieser Datei in einer Form, die DrRacket verarbeiten kann.
#reader(lib "DMdA-beginner-reader.ss" "deinprogramm")((modname prime) (read-case-sensitive #f) (teachpacks ()) (deinprogramm-settings #(#f write repeating-decimal #f #t none explicit #f ())))
; Stelle fest, ob eine Zahl prim ist
(: prime? (natural -> boolean))

(check-expect (prime? 1) #f)
(check-expect (prime? 2) #t)
(check-expect (prime? 4) #f)
(check-expect (prime? 37) #t)

; Prüfe den kleinsten Teiler
#;(define prime?
  (lambda (n) (and (> n 1) (= n (smallest-divisor n)))))

; Berechne den kleinsten Teiler (> 1) einer Zahl
(: smallest-divisor (natural -> natural))

(define smallest-divisor
  (lambda (n) (find-divisor n 2)))

; Finde einen kleinsten Teiler ausgehend von einem kleinsten Kandidaten
(: find-divisor (natural natural -> natural))
(define find-divisor
  (lambda (n test)
    (cond ((> (* test test) n) n)
          ((divides? test n) test)
          (else (find-divisor n (+ test 1))))))

; Prüfe, ob eine Zahl a eine andere Zahl b ganzzahlig teilt
(: divides? (natural natural -> boolean))
(define divides?
  (lambda (a b) (= (remainder b a) 0)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; Berechne aus Argumenten b,e,m den Wert (b^e mod m)
(: expmod (natural natural natural -> natural))
(define expmod
  (lambda (b e m)
    (cond ((= e 0) 1)
          ((even? e) (remainder (square (expmod b (/ e 2) m)) m))
          (else (remainder (* b (expmod b (- e 1) m)) m)))))

(define square (lambda (n) (* n n)))

; Führe den Fermat-Test für die Eingabezahl durch
(: fermat-test (natural -> boolean))
(define fermat-test
  (lambda (n)
    (and (> n 1) (fermat-test-with-random n (+ 1 (random (- n 1)))))))

(: fermat-test-with-random (natural natural -> boolean))
(define fermat-test-with-random
  (lambda (n a) (= (expmod a n n) a)))

; Versuche x-mal den Fermat-Test für eine Zahl
(: fast-prime? (natural natural -> boolean))
(define fast-prime?
  (lambda (n x)
    (cond ((= x 0) #t)
          ((fermat-test n) (fast-prime? n (- x 1)))
          (else #f))))

(define prime?
  (lambda (n) (fast-prime? n 50)))