Primzahlfilter

Aus ProgrammingWiki

(define testliste (lambda (n) (if (= n 0) (list 0) (cons n (testliste (- n 1))))))

Zunächst soll unser Filter an einer generierten Liste natürlicher Zahlen getestet werden.
Ergänzen Sie die erforderlichen Prozeduren:

(define natzahlliste (lambda (n) ...)) (define ungerade? (lambda (n) (= (modulo n 2) 1))) (define my-filter (lambda (proz ls) ...))

(my-filter ungerade? (natzahlliste 50))

ausführen

In einer ersten Idee müsste der Primzahlprüfer die Teilbarkeit der Zahl $n$ durch alle Vorgänger prüfen und als Teiler nur die $1$ finden.

(define teilerliste (lambda (n) (teiler-help n (- n 1)))) (define teiler-help (lambda (n m) ...)) (define primzahl1? (lambda (n) (and (> n 1) (= (length (teilerliste n)) 1))))

(my-filter primzahl1? (natzahlliste 100))

ausführen

Nach weiterführenden Überlegungen kann die Suche aber auf ungerade Teiler bis $\sqrt{n}$ beschränkt werden:

(define primzahl2? (lambda (n) (letrec ([prim? (lambda (n t) (cond [(> t (sqrt n)) #t] [(= (modulo n t) 0) #f] [else (prim? n (+ t 2))]))]) (cond [(= n 2) #t] [(or (< n 2) (= (modulo n 2) 0)) #f] [else (prim? n 3)]))))

Hinweis: Mit letrec lassen sich lokale rekursive Datenstrukturen definieren.

(my-filter primzahl2? (natzahlliste 100))

ausführen

Interessante Untersuchungen lassen sich an Listen mit zufälligen natürlichen Zahlen vornehmen:

(define zufallsliste (lambda (bis n) (if (= n 0) () (cons (+ 1 (random bis)) (zufallsliste bis (- n 1))))))

Hinweis: (random <max>) gibt eine Zufallszahl $z$ zurück mit $0 \le z < max$.

(my-filter primzahl2? (zufallsliste 1000 100))

ausführen

Zurück zu Prozeduren höherer Ordnung (I).