Primzahlfilter

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2010-10-11T08:24:40+00:00. Aktuelle Version

Zunächst soll unser Filter an einer generierten Liste natürlicher Zahlen getestet werden:

(define natzahlliste
  (lambda (n)
    (if (= n 0)
        (list 0)
        (append (natzahlliste (- n 1)) (list n)))))

(define ungerade?
  (lambda (n)
    (= (modulo n 2) 1)))

(define my-filter
  (lambda (proz ls)
    (cond
      [(null? ls) ()]
      [(proz (car ls)) (cons (car ls) (my-filter proz (cdr ls)))]
      [else
       (my-filter proz (cdr ls))])))

<eval id="4b1118006b030"> (my-filter ungerade? (natzahlliste 50)) </eval>

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.
Nach weiterführenden Überlegungen kann die Suche aber auf ungerade Teiler bis \sqrt{n} beschränkt werden:

(define primzahl?
  (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.

<eval id="4b112117825f1"> (my-filter primzahl? (natzahlliste 100)) </eval>

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))))))

<eval id="4b112718aef77"> (my-filter primzahl? (zufallsliste 1000 100)) </eval>

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