Finden Sie Primfaktoren in Python

1. Überblick über die Primfaktorzerlegung
2. Verschiedene Ansätze zum Finden von Primfaktoren in Python

Dieses Tutorial zeigt, wie man eine Primfaktorzerlegung in Python durchführt.

Überblick über die Primfaktorzerlegung

In der Mathematik sind Faktoren einer Zahl diejenigen Zahlen, die die gegebene Zahl teilen können und einen Rest von Null hinterlassen.

Primzahlen sind eindeutige Zahlen mit nur zwei Faktoren, einem und der Zahl selbst. Einige Beispiele für solche Zahlen sind 3,7,11,13 und mehr.

Primfaktorzerlegung bezieht sich auf das Finden aller Primzahlen, die sich multiplizieren, um die ursprüngliche Zahl zu bilden. Wir können ein einfaches Beispiel für die Zahl 6 betrachten.

Die Primfaktorzerlegung dieser Zahl ergibt zwei Faktoren, 2 und 3.

Verschiedene Ansätze zum Finden von Primfaktoren in Python

Wir können Primfaktoren der angegebenen Zahl auf verschiedene Weise finden. Dieser Artikel zeigt drei Methoden, die unten aufgeführt sind:

• Erstellen Sie eine benutzerdefinierte Funktion
• Benutze das Sieb des Eratosthenes
• Verwenden Sie das Modul primefac

Beginnen wir mit dem Erstellen einer benutzerdefinierten Funktion in Python.

Benutzerdefinierte Funktion zur Durchführung der Primfaktorzerlegung

In der Mathematik ist der grundlegendste Ansatz zur Primfaktorzerlegung die wiederholte Division. Wir teilen die Zahl wiederholt durch die Primzahlen. Wir können dies in Python mit verschachtelten Schleifen implementieren.

Die erste Schleife bestimmt, ob eine Zahl eine Primzahl ist oder nicht. Die zweite Schleife teilt diese Primzahl und die gegebene Zahl.

Wenn der Rest Null ist, hängen wir die Primzahl an eine Liste an. Die Funktion gibt die endgültige Liste zurück. Siehe Code unten.

def p_factorization(n):
    i = 2
    lst = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            lst.append(i)
    if n > 1:
        lst.append(n)
    return lst


print(p_factorization(20))

Ausgang:

[2, 2, 5]

Im obigen Beispiel haben wir die Primfaktorzerlegung von 20 zurückgegeben. Der Divisionsoperator // stellt sicher, dass der zurückgegebene Rest eine ganze Zahl ist.

Verwenden Sie das Sieb des Eratosthenes, um die Primfaktorzerlegung durchzuführen

Der Algorithmus Sieb des Eratosthenes gibt alle Primzahlen unterhalb einer gegebenen Zahl zurück.

Es markiert die Werte, die kleiner als die angegebene Zahl sind, und ist durch das Quadrat der Primzahlen teilbar, um alle Primzahlen zurückzugeben, die kleiner als die angegebene Zahl sind.

Wir können es verwenden, um eine Primfaktorzerlegung in Python durchzuführen. Zuerst finden wir die Primzahlen unter der erforderlichen Zahl und dividieren sie dann durch die angegebene Zahl, um ihre Primfaktorzerlegung zu sehen.

Sehen Sie sich den folgenden Codezaun als Beispiel an:

def sieve_of_erast(number):
    maximum = number + 1
    d = dict()
    for i in range(2, maximum):
        d[i] = True

    for i in d:
        factors = range(i, maximum, i)
        for f in factors[1:]:
            d[f] = False
    lst = [i for i in d if d[i] == True]
    return lst


def p_factorization(number):
    x = number
    res = []
    lst = sieve_of_erast(number)
    i = 0
    while i < len(lst):
        if x % lst[i] == 0:
            x = x // lst[i]
            res.append(lst[i])
            i = 0
            if x == 1:
                break
        else:
            i = i + 1
    return res


print(p_factorization(20))

Ausgang:

[2, 2, 5]

Im obigen Codebeispiel erstellen wir zunächst eine Funktion, die das Sieb des Eratosthenes implementiert, um die Primzahlen unterhalb 20 zu finden.

Dann erstellen wir eine weitere Funktion, die diese Liste von Primzahlen verwendet, um die Primfaktorzerlegung derselben zurückzugeben.

Verwenden Sie das primefac-Modul, um die Primfaktorzerlegung durchzuführen

Das Modul primefac dient zur Berechnung von Primzahlen. Es kann umfangreiche Berechnungen effizient handhaben.

Wir können die Funktion primefac() dieses Moduls für die Primfaktorzerlegung verwenden. Sie liefert das Generator-Objekt zurück, das mit dem Konstruktor list in eine Liste umgewandelt werden kann.

Siehe den folgenden Code:

import primefac

print(list(primefac.primefac(20)))

Ausgang:

[2, 2, 5]