Prime Factor Algoritme: C, Python Eksempel

Hva er en Prime Factorization?

Primfaktoren til en gitt noen tall er faktoren som er a primtall. Faktorer når multiplisert gir deg et annet tall. Et primtall er delelig med seg selv eller 1 .

Med andre ord, primfaktorer bestemmes ved å finne hvilke primtall som multipliserer sammen for å danne det opprinnelige tallet.

Eksempel: Primefaktorer på 10 er 2 og 5. Dette er fordi 2X5 =10 og begge 2,5 er primtall.

Finne hovedfaktorene ved hjelp av iterasjon

For å finne primfaktorene til et gitt tall, itererer vi først over alle tallene fra 2 til kvadratroten av tallet, og sjekker deretter om hvert tall er primtall. Så lenge det opprinnelige tallet er delbart med dette primtall, fortsetter vi å legge til dette primtallet for hver iterasjon.

Eksempel:

Hvert primtall større enn 40 skrives i følgende formel: n²+n+41. Så vi kan erstatte n med alle tallene for å finne den tilsvarende primfaktoren. eks 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,...

Hvordan skrive ut en primfaktor for et tall?

• I denne metoden vil vi iterere over tallene fra 2 til kvadratroten av tallet, som nevnt i forrige avsnitt.
• For det må vi sjekke modulen til det opprinnelige tallet på hvert av tallene fra 2 til kvadratroten av n .
• Deretter finner vi listen over primtall som er faktorer av n.
• Denne løsningen er i O(Sqrt(n)) tidskompleksitet.

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

Sil algoritme

Sieve-metoden er avhengig av å lagre den minste primfaktoren av tallene, noe som reduserer kompleksiteten merkbart ved beregning av primfaktorene for et hvilket som helst tall. Sieve-algoritmen finner alle primfaktorene noe effektivt.

• Hovedkonseptet til denne algoritmen er å lagre den minste primfaktoren for hvert tall til det maksimale antallet.
• Vi tar det minste primtall for hvert gitt tall og legger det til settet med primfaktorer.
• Til slutt deler vi på dette primtallet og gjentar disse trinnene til vi når 1.
• Alt dette gjøres i O(log(n)) tidskompleksitet, noe som forbedrer løsningens effektivitet mye.
• Noe som gjør det mulig å beregne primfaktorene for mye større tall enn de vi kunne ha forholdt oss til ved bruk av forrige tilnærming.

Eksempel:

Den andre måten er å sjekke om tallet kan skrives som 6n-1 eller 6n+1 ettersom alle andre primtall enn 2 og 3 skal skrives i en av de to formlene. f.eks. 5=6(1)-1, 19=6(3)+1,….

algoritme:

Definer en matrise for å lagre den minste primfaktoren for hvert tall med indeksverdien som en startverdi for hvert element i matrise.

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 Hovedfaktorer ved bruk av iterasjon

Her vil vi vise en kode i Python språk for å finne primfaktorene til et gitt tall i en iterativ metode:

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)

Utgang:

Enter the number you want: 4
4

Python Hovedfaktorer ved bruk av rekursjon

Denne delen viser en kode i Python Språk ved hjelp av silmetoden for å finne primfaktorene til et gitt tall.

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)

Utgang:

Enter the number you want: 4
2
2

C Prime Factors-program ved hjelp av iterasjon

Det er den samme løsningen som den iterative python, men skrevet inn C-språk.

Vi ber brukeren skrive inn tallet, så for hvert tall fra 2 til kvadratroten av dette tallet, må vi sjekke om det er delbart ved å skrive ut alle forekomstene av denne faktoren.

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

Utgang:

Enter the number you want: 2
2

C Prime Factors-program som bruker rekursjon

Dette er den samme løsningen som den rekursive python-løsningen, men skrevet i C.

Vi kan be brukeren om å taste inn nummeret; så bygger vi primtallsgruppen som lagrer den minste primfaktoren for hvert tall. Til slutt kaller vi Prime Factors for rekursiv funksjon, som deler det gitte tallet med den minste primfaktoren og gjenkaller seg selv til den når en.

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

Utgang:

Enter the number you want: 2
2

Noen interessante fakta om primtall

• En av de mest interessante fakta er at ethvert partall annet enn 2 kan være summen av to primtall.
• For eksempel: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … osv.
• Et annet faktum er at det ikke er andre påfølgende primtall enn 2 og 3, da det eneste partall er tallet 2.
• Dessuten kan alle primtallene unntatt 2 og 3 skrives i følgende form: 6 * n + 1 eller 6 * n – 1, der n er et positivt heltall.
• Settet med primfaktorer for et tall er unikt.
• Tall 1 er verken primtall eller sammensatt.
• Primfaktorisering av tall kan bidra til å løse problemer som delbarhet, forenkling av brøker og å finne fellesnevnere for forskjellige brøker.
• En av de spennende bruksområdene for primfaktorisering er også å bryte hemmelige koder som er tallbaserte.