So finden Sie Primfaktoren in Python

Um die Primfaktoren einer ganzen Zahl in Python zu finden, dividieren Sie sie wiederholt durch Primzahlen. Dieser Artikel zeigt eine eigene Funktion zur Probedivision, einen Ansatz mit dem Sieb des Eratosthenes und das Drittanbieter-Paket primefac. Die Faktoren werden als Liste zurückgegeben, wobei wiederholte Faktoren mitgezählt werden.

Überblick über die Primfaktorzerlegung

Ein Faktor einer ganzen Zahl teilt sie ohne Rest. Eine Primzahl ist größer als 1 und hat genau zwei positive Faktoren: 1 und sich selbst. Zum Beispiel sind 3, 7, 11 und 13 prim.

Die Primfaktorzerlegung schreibt eine ganze Zahl größer als 1 als Produkt von Primzahlen. Da 6 = 2 × 3, sind ihre Primfaktoren 2 und 3. Ein Faktor kann mehrmals vorkommen: 20 = 2 × 2 × 5, also sind seine Primfaktoren [2, 2, 5].

Verschiedene Ansätze zum Finden von Primfaktoren in Python

Wählen Sie die Probedivision für eine kleine, direkte Implementierung; verwenden Sie ein Sieb, wenn Sie zusätzlich Primzahlen bis zu einer Grenze benötigen; oder verwenden Sie primefac, wenn ein Paket die Faktorisierung übernehmen soll. Die folgende eigene Funktion gibt jeden Primfaktor mit seiner Vielfachheit zurück.

Eigene Funktion zur Durchführung der Primfaktorzerlegung

Die Probedivision testet mögliche Teiler in aufsteigender Reihenfolge. Wenn ein Kandidat den verbleibenden Wert teilt, zeichnet die Funktion ihn auf und dividiert ihn heraus, bevor sie erneut testet. Es genügt zu testen, solange das Quadrat des Kandidaten nicht größer ist als der verbleibende Wert: Wenn ein größerer Faktor übrig bliebe, wäre sein gepaarter Faktor bereits gefunden worden. Jeder verbleibende Wert größer als 1 ist prim.

Führen Sie dieses Beispiel mit der ganzen Zahl 20 aus:

def prime_factors(n):
    if n < 1:
        return None

    factors = []
    divisor = 2
    while divisor * divisor <= n:
        if n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        else:
            divisor += 1
    if n > 1:
        factors.append(n)
    return factors


print(prime_factors(20))

[2, 2, 5]

Die Funktion verwendet eine einzige Teilerschleife; sie erzeugt nicht zuerst eine Liste von Primzahlen. Ihre //-Operation hält den verbleibenden Wert ganzzahlig. Das Ergebnis None kennzeichnet nicht unterstützte Werte unter 1; prime_factors(1) gibt [] zurück, weil 1 keine Primfaktoren hat.

Das Sieb des Eratosthenes zur Durchführung der Primfaktorzerlegung verwenden

Das Sieb des Eratosthenes findet alle Primzahlen bis zu einer Grenze, indem es die Vielfachen jeder Primzahl markiert, beginnend mit dem Quadrat dieser Primzahl. Um eine ganze Zahl zu faktorisieren, bauen Sie das Sieb nur bis zu dieser ganzen Zahl auf und dividieren dann jede aufgeführte Primzahl so oft wie möglich heraus. Dieser Ansatz ist nützlich, wenn die Primzahlliste wiederverwendet wird; ein Sieb nur zum Faktorisieren eines einzelnen Wertes aufzubauen kann unnötige Arbeit verursachen. Das folgende Sieb gibt Primzahlen bis einschließlich seiner Grenze zurück. Es ist ein Syntax- und Algorithmusbeispiel ohne angezeigte Ausgabe.

def primes_up_to(limit):
    if limit < 2:
        return []

    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    candidate = 2
    while candidate * candidate <= limit:
        if is_prime[candidate]:
            for multiple in range(candidate * candidate, limit + 1, candidate):
                is_prime[multiple] = False
        candidate += 1
    return [number for number, prime in enumerate(is_prime) if prime]


def factor_with_sieve(number):
    if number < 1:
        return None
    factors = []
    for prime in primes_up_to(number):
        while number % prime == 0:
            factors.append(prime)
            number //= prime
    return factors

Weitere Einzelheiten zum Sieb des Eratosthenes finden Sie in der zugehörigen Anleitung. Wie bei der eigenen Funktion gibt diese Version [] für 1 und None für Werte unter 1 zurück.

Das Modul primefac zur Durchführung der Primfaktorzerlegung verwenden

primefac ist ein externes Python-Paket, daher muss es in der Umgebung installiert sein, die Ihr Programm ausführt. Seine Funktion primefac() liefert Primfaktoren; wandeln Sie das Ergebnis in eine Liste um, wenn Sie es als Sequenz anzeigen oder speichern müssen: list(primefac.primefac(20)). Diese Option belässt die Faktorisierungslogik im Paket statt in einer eigenen Funktion. Der Paketaufruf wird inline gezeigt, weil die eigenständigen Beispiele dieses Artikels diese externe Abhängigkeit nicht enthalten oder installieren.