Prime Factor Algoritme: C, Python Eksempel

Hvad er en Prime Factorization?

Primfaktoren for en given enhver tal er den faktor, der er a primtal. Faktorer, når de ganges, giver dig et andet tal. Et primtal er deleligt med sig selv eller 1 .

Med andre ord bestemmes primtal ved at finde ud af, hvilke primtal der multipliceres sammen for at danne det oprindelige tal.

Eksempel: Primfaktorer på 10 er 2 og 5. Dette skyldes, at 2X5 =10 og begge 2,5 er primtal.

Find de primære faktorer ved hjælp af iteration

For at finde primfaktorerne for et givet tal, itererer vi først over alle tallene fra 2 indtil kvadratroden af ​​tallet, og kontrollerer derefter, om hvert tal er primtal. Så længe det oprindelige tal kan divideres med dette primtal, bliver vi ved med at tilføje dette primtal for hver iteration.

Eksempel:

Hvert primtal større end 40 skrives i følgende formel: n²+n+41. Så vi kan erstatte n med alle tallene for at finde den tilsvarende primfaktor. fx 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,...

Hvordan udskriver man en primfaktor for et tal?

• I denne metode vil vi iterere over tallene fra 2 til kvadratroden af ​​tallet, som nævnt i forrige afsnit.
• Til det skal vi kontrollere modulet af det oprindelige tal på hvert af tallene fra 2 indtil kvadratroden af ​​n .
• Derefter finder vi listen over primtal, der er faktorer af n.
• Denne løsning 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

Sigte algoritme

Sigtemetoden er afhængig af at gemme den mindste primfaktor af tallene, hvilket reducerer kompleksiteten mærkbart, når primfaktorerne beregnes for ethvert tal. Sigtealgoritmen finder alle primfaktorerne noget effektivt.

• Hovedkonceptet for denne algoritme er at gemme den mindste primfaktor for hvert tal indtil det maksimale antal.
• Vi tager det mindste primtal for hvert givet tal og lægger det til sættet af primfaktorer.
• Til sidst dividerer vi med dette primtal og gentager disse trin, indtil vi når 1.
• Dette er alt sammen gjort i O(log(n)) tidskompleksitet, hvilket forbedrer løsningens effektivitet meget.
• Hvilket gør det muligt at beregne primfaktorerne for meget større tal end dem, vi kunne have beskæftiget os med ved hjælp af den tidligere tilgang.

Eksempel:

Den anden måde er at kontrollere, om tallet kan skrives som 6n-1 eller 6n+1, da ethvert andet primtal end 2 og 3 skal skrives i en af ​​de to formler. fx 5=6(1)-1, 19=6(3)+1,….

Algoritme:

Definer et array-array for at gemme den mindste primfaktor af hvert tal med indeksværdien som en startværdi for hvert element i matrix.

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 Primære faktorer ved hjælp af iteration

Her vil vi vise en kode i Python sprog til at finde primfaktorerne for et givet tal 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)

Output:

Enter the number you want: 4
4

Python Primære faktorer, der bruger rekursion

Dette afsnit viser en kode i Python Sprog ved hjælp af sigtemetoden til at finde primfaktorerne for et givet tal.

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-program ved hjælp af iteration

Det er den samme løsning som den iterative python, men skrevet i C-sprog.

Vi beder brugeren om at indtaste tallet, og for hvert tal fra 2 til kvadratroden af ​​dette tal skal vi kontrollere, om det er deleligt ved at udskrive alle forekomster af denne faktor.

#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-program ved hjælp af rekursion

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

Vi kan bede brugeren om at indtaste nummeret; derefter bygger vi primtal-arrayet, der gemmer den mindste primfaktor af hvert tal. Til sidst kalder vi Prime Factors for rekursiv funktion, som dividerer det givne tal med sin mindste primfaktor og genkalder sig selv, indtil man når én.

#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

Nogle interessante fakta om primtal

• En af de mest interessante fakta er, at ethvert lige tal bortset fra 2 kan være summen af ​​to primtal.
• For eksempel: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … osv.
• En anden kendsgerning er, at der ikke er andre på hinanden følgende primtal end 2 og 3, da det eneste lige primtal er tallet 2.
• Desuden kan alle primtal undtagen 2 og 3 skrives i følgende form: 6 * n + 1 eller 6 * n – 1, hvor n er et positivt heltal.
• Sættet af primfaktorer for et tal er unikt.
• Nummer 1 er hverken primtal eller sammensat.
• Primfaktorisering af tal kan hjælpe med at løse problemer som delelighed, forenkling af brøker og at finde fællesnævnere for forskellige brøker.
• En af de spændende anvendelser af primfaktorisering er også at bryde hemmelige koder, der er talbaserede.