;; 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 ())))
; Primzahltest: Teste, ob eine natürliche Zahl prim ist
(: prime? (natural -> boolean))

(check-expect (prime? 1) #f)
(check-expect (prime? 2) #t)
(check-expect (prime? 42) #f)
(check-expect (prime? 43) #t)

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

; Berechne den kleinsten Teiler einer Zahl
(: smallest-divisor (natural -> natural))
(define smallest-divisor
  (lambda (n) (find-divisor n 2)))

(: find-divisor (natural natural -> natural))
(define find-divisor
  (lambda (n test)
    (cond ((> (square test) n) n)
          ((divides? test n) test)
          (else (find-divisor n (+ test 1))))))

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

(define square (lambda (x) (* x x)))

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

; Berechne aus den Argumenten b,e,m den Wert (b^e mod m) (schnell!)
(: 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)))))

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

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

; Versuche x-mal den Fermat-Test durchzuführen:
(: 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)))