;; 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? 7) #t)
(check-expect (prime? 25) #f)
(check-expect (prime? 43) #t)

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

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

; Finde den kleinsten Teiler einer Zahl ausgehend von einem Testwert:
(: 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 die erste Zahl die zweite ganzzahlig teilt.
(: divides? (natural natural -> boolean))
(define divides?
  (lambda (a b)
    (= (remainder b a) 0)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Berechne aus den Argumenten b, e, m den Wert (b^e mod m):
; (mit m>1)
(: expmod (natural natural natural -> natural))
; wie schnelles Potenzieren, aber mit modulo:
(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 (x) (* x x)))

; Führe Fermat-Test mit einer Zufallszahl 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)))

; Führe mehrfach den Fermat-Test aus (2. Argument: wie oft?)
(: 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)))