Grundlagen der funktionsorientierten Programmierung mit SCHEME/Primfaktorzerlegung

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
'''Autorin: Corinna Kocksch (2014)'''

Es gibt nach wie vor intensive Bemühungen, große natürliche Zahlen ''effizient'' in ihre Primfaktoren zu zerlegen (vgl. auch [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das RSA-Verfahren|Verschlüsselung von Daten mit dem RSA-Verfahren]]).
Nachfolgend soll ein Algorithmus vorgestellt werden, der bereits recht effizient diese Primfaktorzerlegung vornimmt.

== Primzahlprüfer ==

Zur Konstruktion eines [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Primzahlfilter|Primzahlfilters]] haben wir bereits ein Prädikat kennen gelernt, das eine effiziente Primzahlprüfung zulässt:

<code id="53c0f0576d5c5">
(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)]))))
</code>

<run id="53c0f0576d6da">
(primzahl? (- (expt 2 31) 1)) 
</run>

== Algorithmus zur Primfaktorzerlegung ==

Damit lässt sich nun auch eine effiziente Primfaktorzerlegung realisieren:

<code id="53c0f25f9a7c6">
(define primfaktoren
  (lambda (z)
    (letrec 
        ([zerlegung
          (lambda (z p)
            (cond 
              [(< z 2) #f]
              [(primzahl? z) (list z)]
              [(= (modulo z 2) 0) (cons 2 (zerlegung (quotient z 2) p))]
              [(primzahl? p)
               (if (= (modulo z p) 0) 
                   (cons p (zerlegung (quotient z p) p))
                   (zerlegung z (+ p 2)))]
              [else
               (zerlegung z (+ p 2))]))])              
      (zerlegung z 3))))
</code>

<run id="53c0f0576d751">
(primfaktoren 156788717)
</run>

Zurück zum [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Der Algorithmusbegriff|Algorithmusbegriff]].