Primfaktor-Algorithmus: C, Python Beispiel

Was ist eine Primfaktorzerlegung?

Der Primfaktor einer Zahl ist ein Faktor, der selbst ein Faktor ist. Primzahl, nur durch 1 und sich selbst teilbar.

Ejemplo: Die Primfaktoren von 10 sind 2 und 5, da 2 × 5 = 10.

Finden der Primfaktoren mithilfe der Iteration

Iteriere von 2 bis zur Quadratwurzel von n und prüfe die Teilbarkeit. Solange n durch den aktuellen Kandidaten teilbar ist, dividiere und gib das Ergebnis aus.

Ejemplo: Jede Primzahl größer als 40 passt in n²+n+41, also n = 0, 1, 2 ergibt 41, 43, 47.

Wie drucke ich einen Primfaktor einer Zahl aus?

• Iteriere die Zahlen von 2 bis sqrt(n).
• Prüfen Sie den Betrag von n für jeden Kandidaten; ein Rest von Null bedeutet, dass der Kandidat ein Primfaktor ist.
• Sammle alle Primzahlen, die n teilen.
• Die Routine hat eine Zeitkomplexität von O(sqrt(n)).

Algorithmus:

Set a counter i to 2
While i <= sqrt(n):
    While n % i == 0:
        n = n / i
        print i
    i = i + 1
if n > 1:
    print n

Sieb-Algorithmus

Das Siebverfahren speichert den kleinsten Primfaktor jeder Zahl bis zu einer maximalen Grenze und reduziert so die Faktorisierungskosten nach der Vorberechnung erheblich.

• Notieren Sie den kleinsten Primfaktor jeder ganzen Zahl bis zum maximalen Grenzwert.
• Nimm die kleinste Primzahl und füge sie der Faktorenmenge hinzu.
• Teile die Zahl durch diese Primzahl und wiederhole dies, bis das Ergebnis 1 ist.
• Jede Abfrage hat eine Laufzeit von etwa O(log n).

Ejemplo: Eine Primzahl außer 2 und 3 hat die Form 6n-1 oder 6n+1. Zum Beispiel: 5 = 6(1)-1 und 19 = 6(3)+1.

Algorithmus: definieren Sie Array speichert den kleinsten Primfaktor jeder Zahl, wobei der Index als Anfangswert für jedes Element verwendet wird.

Set array[1] to 1
Set i to 2
While i*i <= max_number:
    If array[i] == i:
        Set j to i*i
        While j <= max_number:
            If array[j] == j:
                array[j] = i
            j = j + i
    i = i + 1
while the_number != 1:
    print array[the_number]
    the_number = the_number / array[the_number]

Ähnliche Artikel

• Diagrammdatenstruktur und Algorithms
• Problem mit dem reisenden Verkäufer
• Algorithmus der Bisektionsmethode
• Bucket-Sortieralgorithmus

Python Primfaktoren durch Iteration

Folgende Python Der Code ermittelt Primfaktoren mithilfe der iterativen Probedivisionsmethode:

import math
def PrimeFactors(n):
    for i in range(2, int(math.sqrt(n)) + 1, 1):
        while n % i == 0:  # find all the occurrences of a prime factor
            print((int)(i))
            n = n // i
    if n != 1:  # if the number was originally a prime
        print((int)(n))
n = (int)(input("Enter the number you want: "))
PrimeFactors(n)

Ausgang:

Enter the number you want: 4
2
2

Python Primfaktoren durch Rekursion

Das Python Der unten stehende Code verwendet das Siebverfahren, um die Primfaktoren einer gegebenen Zahl zu finden.

import math
High = (int)(1e5 + 7)
array = [0 for i in range(High)]

# generate smallest prime factors
def Sieve():
    for i in range(1, High):
        array[i] = i
    for i in range(2, math.ceil(math.sqrt(High))):
        if array[i] == i:
            for j in range(i * i, High, i):
                if array[j] == j:
                    array[j] = i

def PrimeFactors(n):  # divide until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n / array[n]))

Sieve()
n = (int)(input("Enter the number you want: "))
PrimeFactors(n)

Ausgang:

Enter the number you want: 4
2
2

C-Primfaktorprogramm mit Iteration

Die gleiche iterative Lösung, geschrieben in C: Geben Sie eine Zahl ein, und prüfen Sie dann für jeden Kandidaten von 2 bis sqrt(n) die Teilbarkeit und geben Sie jedes Vorkommen eines Primfaktors aus.

#include <stdio.h>
int main()
{
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    for (int i = 2; i * i <= n; i++)
    {
        while (n % i == 0)  // find all the occurrences of a prime factor
        {
            printf("%d\n", i);
            n /= i;
        }
    }
    if (n != 1)  // if the number was originally a prime
    {
        printf("%d", n);
    }
    return 0;
}

Ausgang:

Enter the number you want: 2
2

C-Primfaktorprogramm mit Rekursion

Die rekursive C-Version spiegelt die Python eins: Erstelle ein Array der kleinsten Primfaktoren und teile dann rekursiv durch diesen Faktor, bis n den Wert 1 erreicht.

#include <stdio.h>
int Max = 100007;
int array[100007];

void Sieve()  // smallest prime factors up to Max
{
    for (int i = 1; i < Max; i++)
        array[i] = i;
    for (int i = 2; i * i <= Max; i++)
    {
        if (array[i] == i)
        {
            for (int j = i * i; j < Max; j += i)
            {
                if (array[j] == j)
                    array[j] = i;
            }
        }
    }
}

void PrimeFactors(int n)
{
    if (n == 1)  // divide until we reach 1
        return;
    printf("%d\n", array[n]);
    PrimeFactors(n / array[n]);
}

int main()
{
    Sieve();
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    PrimeFactors(n);
    return 0;
}

Ausgang:

Enter the number you want: 2
2

Einige interessante Fakten über Primzahlen

• Jede gerade Zahl außer 2 kann als Summe zweier Primzahlen geschrieben werden (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• Es gibt keine aufeinanderfolgenden Primzahlen außer 2 und 3, da 2 die einzige gerade Primzahl ist.
• Alle Primzahlen außer 2 und 3 haben die Form 6n + 1 oder 6n − 1, wobei n eine positive ganze Zahl ist.
• Die Menge der Primfaktoren einer Zahl ist eindeutig.
• Die Zahl 1 ist weder eine Primzahl noch eine zusammengesetzte Zahl.
• Die Primfaktorzerlegung hilft bei der Teilbarkeit, der Vereinfachung von Brüchen und dem Finden gemeinsamer Nenner.
• Die Primfaktorzerlegung ist auch die Grundlage zahlenbasierter kryptographischer Codes.

Häufig gestellte Fragen