Prime Factor-algoritme: C, Python Voorbeeld

Wat is een priemfactorisatie?

De priemfactor van een gegeven elke getal is de factor die a is priemgetal. Als de factoren worden vermenigvuldigd, krijgt u een ander getal. Een priemgetal is deelbaar door zichzelf of door 1.

Met andere woorden, priemfactoren worden bepaald door te bepalen welke priemgetallen met elkaar vermenigvuldigd het oorspronkelijke getal vormen.

Voorbeeld: De priemfactoren van 10 zijn 2 en 5. Dit komt omdat 2X5 = 10 en 2,5 en XNUMX allebei priemgetallen zijn.

Het vinden van de priemfactoren met behulp van iteratie

Om de priemfactoren van een gegeven getal te vinden, itereren we eerst over alle getallen van 2 tot de vierkantswortel van het getal en controleren dan of elk getal priem is. Zolang het oorspronkelijke getal deelbaar is door dit priemgetal, blijven we dit priemgetal bij elke iteratie toevoegen.

Voorbeeld:

Elk priemgetal groter dan 40 wordt in de volgende formule geschreven: n²+n+41. We kunnen dus n vervangen door alle getallen om de corresponderende priemfactor te vinden. Bijvoorbeeld 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

Hoe druk ik een priemfactor van een getal af?

• Bij deze methode itereren we over de getallen van 2 tot aan de vierkantswortel van het getal, zoals vermeld in de vorige sectie.
• Hiervoor moeten we de modulus van het oorspronkelijke getal controleren voor elk van de getallen van 2 tot en met de vierkantswortel van n.
• Vervolgens vinden we de lijst met priemgetallen die factoren van n zijn.
• Deze oplossing heeft een tijdcomplexiteit van O(Sqrt(n)).

Algoritme:

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

Zeef algoritme

De zeefmethode is gebaseerd op het opslaan van de kleinste priemfactor van de getallen, wat de complexiteit merkbaar vermindert bij het berekenen van de priemfactoren voor elk getal. Het zeefalgoritme vindt alle priemfactoren enigszins efficiënt.

• Het belangrijkste concept van dit algoritme is om de kleinste priemfactor van elk getal op te slaan tot het maximale getal.
• We nemen het kleinste priemgetal voor elk gegeven getal en voegen dit toe aan de reeks priemfactoren.
• Ten slotte delen we door dit priemgetal en herhalen we deze stappen totdat we 1 bereiken.
• Dit alles gebeurt met een tijdscomplexiteit van O(log(n)), waardoor de efficiëntie van de oplossing aanzienlijk wordt verbeterd.
• Hierdoor is het mogelijk om de priemfactoren van veel grotere getallen te berekenen dan met de vorige aanpak mogelijk was geweest.

Voorbeeld:

De tweede manier is om te controleren of het getal kan worden geschreven als 6n-1 of 6n+1, aangezien elk priemgetal anders dan 2 en 3 in een van de twee formules moet worden geschreven. bijv. 5=6(1)-1, 19=6(3)+1,… .

Algoritme:

Definieer een array-array om de kleinste priemfactor van elk getal op te slaan, met de indexwaarde als beginwaarde voor elk element van de reeks.

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 Prime-factoren met behulp van iteratie

Hier laten we een code zien in Python taal om de priemfactoren van een bepaald getal in een iteratieve methode te vinden:

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)

Output:

Enter the number you want: 4
4

Python Priemfactoren met behulp van recursie

In deze sectie wordt een code weergegeven Python taal de zeefmethode gebruiken om de priemfactoren van een bepaald getal te vinden.

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)

Output:

Enter the number you want: 4
2
2

C Prime Factors-programma met behulp van iteratie

Het is dezelfde oplossing als de iteratieve Python-oplossing, maar dan geschreven C taal.

We vragen de gebruiker om het getal in te voeren. Vervolgens moeten we voor elk getal van 2 tot de wortel van dit getal controleren of het deelbaar is door alle exemplaren van deze factor af te drukken.

#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;
}

Output:

Enter the number you want: 2
2

C Prime Factors-programma met behulp van recursie

Dit is dezelfde oplossing als de recursieve python-oplossing, maar geschreven in C.

We kunnen de gebruiker vragen het nummer in te voeren; Vervolgens bouwen we de matrix met priemgetallen waarin de kleinste priemfactor van elk getal wordt opgeslagen. Ten slotte noemen we de priemfactoren recursieve functie, die het gegeven getal deelt door de kleinste priemfactor en zichzelf herinnert totdat het één bereikt.

#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;
}

Output:

Enter the number you want: 2
2

Enkele interessante feiten over priemgetallen

• Een van de interessantste feiten is dat elk even getal, behalve 2, de som van twee priemgetallen kan zijn.
• Bijvoorbeeld: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … enz.
• Een ander feit is dat er geen andere opeenvolgende priemgetallen zijn dan 2 en 3, aangezien het enige even priemgetal het getal 2 is.
• Bovendien kunnen alle priemgetallen behalve 2 en 3 in de volgende vorm worden geschreven: 6 * n + 1 of 6 * n – 1, waarbij n een positief geheel getal is.
• De verzameling priemfactoren van een getal is uniek.
• Nummer 1 is noch priemgetal, noch samengesteld.
• Het ontbinden van getallen in priemfactoren kan helpen bij het oplossen van problemen zoals deelbaarheid, het vereenvoudigen van breuken en het vinden van de gemeenschappelijke deler van verschillende breuken.
• Een van de opwindende toepassingen van priemfactorisatie is ook het doorbreken van geheime codes die op getallen zijn gebaseerd.