Primfaktor-Algorithmus: C, Python Beispiel

Was ist eine Primfaktorzerlegung?

Der Primfaktor einer gegebenen Sache für Zahl ist der Faktor, der a ist Primzahl. Multipliziert man die Faktoren, erhält man eine andere Zahl. Eine Primzahl ist durch sich selbst oder 1 teilbar.

Mit anderen Worten werden Primfaktoren bestimmt, indem man herausfindet, welche Primzahlen miteinander multipliziert die ursprüngliche Zahl ergeben.

Beispiel: Die Primfaktoren von 10 sind 2 und 5. Das liegt daran, dass 2X5 =10 und sowohl 2,5 als auch XNUMX Primzahlen sind.

Finden der Primfaktoren mithilfe der Iteration

Um die Primfaktoren einer gegebenen Zahl zu finden, iterieren wir zunächst über alle Zahlen von 2 bis zur Quadratwurzel der Zahl und prüfen dann, ob jede Zahl eine Primzahl ist. Solange die ursprüngliche Zahl durch diese Primzahl teilbar ist, addieren wir diese Primzahl bei jeder Iteration weiter.

Ejemplo:

Jede Primzahl größer als 40 wird in der folgenden Formel geschrieben: n²+n+41. Wir können also n durch alle Zahlen ersetzen, um den entsprechenden Primfaktor zu finden. Beispiel: 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

Wie drucke ich einen Primfaktor einer Zahl aus?

• Bei dieser Methode iterieren wir über die Zahlen von 2 bis zur Quadratwurzel der Zahl, wie im vorherigen Abschnitt erwähnt.
• Dazu müssen wir den Modul der ursprünglichen Zahl für jede der Zahlen von 2 bis zur Quadratwurzel von n überprüfen.
• Dann finden wir die Liste der Primzahlen, die Faktoren von n sind.
• Die Zeitkomplexität dieser Lösung beträgt 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

Die Siebmethode basiert auf der Speicherung des kleinsten Primfaktors der Zahlen, was die Komplexität bei der Berechnung der Primfaktoren für jede Zahl deutlich reduziert. Der Siebalgorithmus findet alle Primfaktoren relativ effizient.

• Das Hauptkonzept dieses Algorithmus besteht darin, den kleinsten Primfaktor jeder Zahl bis zur maximalen Zahl zu speichern.
• Wir nehmen für jede gegebene Zahl die kleinste Primzahl und addieren sie zur Menge der Primfaktoren.
• Abschließend dividieren wir durch diese Primzahl und wiederholen diese Schritte, bis wir 1 erreichen.
• Dies alles geschieht mit einer Zeitkomplexität von O(log(n)), was die Effizienz der Lösung erheblich verbessert.
• Dadurch ist es möglich, die Primfaktoren viel größerer Zahlen zu berechnen, als wir mit dem vorherigen Ansatz hätten behandeln können.

Ejemplo:

Die zweite Möglichkeit besteht darin, zu prüfen, ob die Zahl als 6n-1 oder 6n+1 geschrieben werden kann, da jede andere Primzahl als 2 und 3 in eine der beiden Formeln geschrieben werden sollte. z. B. 5=6(1)-1, 19=6(3)+1,… .

Algorithmus:

Definieren Sie ein Array-Array, um den kleinsten Primfaktor jeder Zahl mit dem Indexwert als Anfangswert für jedes Element zu speichern Array.

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]

Python Primfaktoren durch Iteration

Hier zeigen wir einen Code in Python Sprache, um die Primfaktoren einer gegebenen Zahl in einem iterativen Verfahren zu finden:

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
4

Python Primfaktoren durch Rekursion

Dieser Abschnitt zeigt einen Code in Python Sprache Verwenden Sie die Siebmethode, um die Primfaktoren einer bestimmten Zahl zu ermitteln.

import math
High = (int)(1e5+7)
array=[0 for i in range(High)]
# function to generate all the smallest prime 
def Sieve():
#factors of the numbers until the maximum  number
    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):
#We will keep dividing until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n/array[n]))
#Here we call the function after dividing it by this prime
Sieve()
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)

Ausgang:

Enter the number you want: 4
2
2

C-Primfaktorprogramm mit Iteration

Es ist die gleiche Lösung wie die iterative Python-Lösung, jedoch in geschrieben C Sprache.

Wir bitten den Benutzer, die Zahl einzugeben. Anschließend müssen wir für jede Zahl von 2 bis zur Quadratwurzel dieser Zahl prüfen, ob sie teilbar ist, indem wir alle Vorkommen dieses Faktors ausdrucken.

#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

Dies ist die gleiche Lösung wie die rekursive Python-Lösung, jedoch in C geschrieben.

Wir können den Benutzer bitten, die Nummer einzugeben; Anschließend erstellen wir das Primzahlarray, das den kleinsten Primfaktor jeder Zahl speichert. Schließlich nennen wir die rekursive Funktion Primfaktoren, die die gegebene Zahl durch ihren kleinsten Primfaktor dividiert und sich selbst zurückruft, bis sie Eins erreicht.

#include <stdio.h>
int Max = 100007;
int array[100007];
void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number
{
    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)//keep dividing until we reach 1
    {
        return;
    }
    printf("%d\n",array[n]);
    PrimeFactors(n/array[n]);//call the function after dividing by //this prime
}
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

• Eine der interessantesten Tatsachen ist, dass jede gerade Zahl außer 2 die Summe zweier Primzahlen sein kann.
• Zum Beispiel: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … usw.
• Eine weitere Tatsache ist, dass es außer 2 und 3 keine aufeinanderfolgenden Primzahlen gibt, da die einzige gerade Primzahl die Zahl 2 ist.
• Außerdem können alle Primzahlen außer 2 und 3 in der folgenden Form geschrieben werden: 6 * n + 1 oder 6 * n – 1, wobei n eine positive ganze Zahl ist.
• Die Menge der Primfaktoren einer Zahl ist eindeutig.
• Nummer 1 ist weder eine Primzahl noch eine zusammengesetzte Zahl.
• Durch die Primfaktorzerlegung von Zahlen können Probleme wie Teilbarkeit, Vereinfachen von Brüchen und Finden gemeinsamer Nenner verschiedener Brüche gelöst werden.
• Eine der spannenden Anwendungen der Primfaktorzerlegung ist außerdem das Aufschlüsseln von Geheimcodes, die auf Zahlen basieren.