Faktorisierungsmethode von Fermat

Die Faktorisierungsmethode von Fermat berechnet zu einer ungeraden, zusammengesetzten Zahl n zwei Teiler a und b, für die gilt a * b = n. (Quelle)

Der Algorithmus

Folgendes ist zu bearbeiten:

• Hier folgt Quelltext...

Die Implementierung

Hier folgt Quelltext. Eine sehr frühe Implementierung.

import math


def __faktorisieren(n):
    ''' Funktion, die eine Zahl n faktorisiert,
    sobald 2 ganzzahlige Faktoren gefunden wurden,
    dann Rueckgabe der beiden Werte.
    Es werden nicht alle Faktoren fuer die Zahl
    n gesucht!

    '''
    n = int(n)
    zahl = math.sqrt(n)

    if int(zahl) == zahl:
        a = n // zahl
        b = zahl
        return a, b
    else:
        zahl = int(zahl)
        
        for i in range(zahl,n+1):

            if n / i == n // i:
                a = n // i
                b = i
                return a, b


def primfaktoren_bestimmen(n):
    ''' Funktion, die fuer eine Zahl n die
    Primzahlenfaktorisierung erledigt

    '''

    primzahlen = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    result = [] # Nimmt das Ergebnis auf
    queue = []

    if n in primzahlen:
        return "Primzahl!"
    elif n == 1:
        print("Keine Faktorisierung möglich!")
        return n
    else:
        a, b = __faktorisieren(n)
        queue.append(a)
        queue.append(b)
        
        while True:
            
            x = queue.pop()
            
            if x in primzahlen:
                result.append(x)
            else:
                a, b = __faktorisieren(x)
                queue.append(a)
                queue.append(b)
            if len(queue) == 0:
                result.sort()
                result = [int(x) for x in result]
                return result


for i in range(2,100):
    print(i, primfaktoren_bestimmen(i))

Ich habe eine Primzahlliste für den Zahlenraum zwischen 1 und 100 beigegeben, um zu prüfen, ob die jeweilige Zahl noch einmal faktorisiert werden muss.

Eigentlich müsste das Skript aber auch selbst Primzahlen erkennen können: Eine Zahl n ist nämlich dann eine Primzahl, wenn als Faktoren die Zahlen 1 und n zurückkommen. Die Prüfung könnte auch dann an dieser Stelle enden und die Zahl n könnte der Ergebnisliste result beigegeben werden. Das ist (noch) nicht implementiert, wäre aber gerade für besonders große Zahlen interessant.

Zu diesem Eintrag gehört dieser Thread im Python-Forum.