Primfaktoralgoritm: C, Python Exempelvis

Vad är en Prime Factorization?

Primfaktorn för en given vilken som helst antal är faktorn som är a primtal. Faktorer när de multipliceras ger dig ett annat tal. Ett primtal är delbart med sig självt eller 1 .

Med andra ord bestäms primtalsfaktorer genom att hitta vilka primtal som multipliceras tillsammans för att bilda det ursprungliga talet.

Exempelvis: Primfaktorer på 10 är 2 och 5. Detta beror på att 2X5 =10 och båda 2,5 är primtal.

Hitta de primära faktorerna med iteration

För att hitta primtalsfaktorerna för ett givet tal, itererar vi först över alla tal från 2 till kvadratroten av talet och kontrollerar sedan om varje tal är primtal. Så länge det ursprungliga talet är delbart med detta primtal fortsätter vi att lägga till detta primtal med varje iteration.

Exempelvis:

Varje primtal större än 40 skrivs i följande formel: n²+n+41. Så vi kan ersätta n med alla tal för att hitta motsvarande primfaktor. ex 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,...

Hur skriver man ut en primtalsfaktor för ett tal?

• I den här metoden kommer vi att iterera över talen från 2 till kvadratroten av talet, som nämndes i föregående avsnitt.
• För det måste vi kontrollera modulen för det ursprungliga talet på vart och ett av talen från 2 till kvadratroten av n .
• Sedan hittar vi listan med primtal som är faktorer för n.
• Denna lösning är i O(Sqrt(n)) tidskomplexitet.

Algoritm:

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

Sållalgoritm

Sieve-metoden bygger på att lagra den minsta primfaktorn av talen, vilket minskar komplexiteten märkbart vid beräkning av primtalsfaktorerna för vilket tal som helst. Sieve-algoritmen hittar alla primtalsfaktorer något effektivt.

• Huvudkonceptet för denna algoritm är att lagra den minsta primfaktorn för varje tal tills det maximala antalet.
• Vi tar det minsta primtal för varje givet tal och adderar det till uppsättningen av primtalsfaktorer.
• Slutligen delar vi med detta primtal och upprepar dessa steg tills vi når 1.
• Allt detta görs i O(log(n)) tidskomplexitet, vilket förbättrar lösningens effektivitet mycket.
• Vilket gör det möjligt att beräkna primtalsfaktorerna för mycket större tal än de vi kunde ha hanterat med det tidigare tillvägagångssättet.

Exempelvis:

Det andra sättet är att kontrollera om talet kan skrivas som 6n-1 eller 6n+1 eftersom alla andra primtal än 2 och 3 ska skrivas i en av de två formlerna. t.ex. 5=6(1)-1, 19=6(3)+1,….

Algoritm:

Definiera en matris för att lagra den minsta primfaktorn för varje tal med indexvärdet som ett initialt värde för varje element i 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 Primära faktorer som använder iteration

Här kommer vi att visa en kod i Python språk för att hitta primtalsfaktorerna för ett givet tal i en iterativ metod:

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)

Produktion:

Enter the number you want: 4
4

Python Primära faktorer som använder rekursion

Det här avsnittet visar en kod i Python språk använda siktmetoden för att hitta primtalsfaktorerna för ett 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)

Produktion:

Enter the number you want: 4
2
2

C Prime Factors-program med iteration

Det är samma lösning som den iterativa python men inskriven C-språk.

Vi ber användaren att ange siffran, och för varje nummer från 2 till kvadratroten av detta nummer måste vi kontrollera om det är delbart genom att skriva ut alla förekomster av denna 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;
}

Produktion:

Enter the number you want: 2
2

C Prime Factors-program som använder rekursion

Detta är samma lösning som den rekursiva python men skriven i C.

Vi kan be användaren att ange numret; sedan bygger vi primtalsmatrisen som lagrar den minsta primtalsfaktorn för varje tal. Slutligen kallar vi primtalsfaktorerna för rekursiv funktion, som delar det givna talet med sin minsta primtalsfaktor och återkallar sig själv tills 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;
}

Produktion:

Enter the number you want: 2
2

Några intressanta fakta om primtal

• En av de mest intressanta fakta är att alla andra jämna tal än 2 kan vara summan av två primtal.
• Till exempel: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … osv.
• Ett annat faktum är att det inte finns några på varandra följande primtal förutom 2 och 3, eftersom det enda jämna primtalet är talet 2.
• Alla primtal utom 2 och 3 kan också skrivas i följande form: 6 * n + 1 eller 6 * n – 1, där n är ett positivt heltal.
• Uppsättningen av primtalsfaktorer för ett tal är unik.
• Tal 1 är varken primtal eller sammansatt.
• Primfaktorisering av tal kan hjälpa till att lösa problem som delbarhet, förenkla bråk och hitta gemensamma nämnare för olika bråk.
• En av de spännande användningarna av primtalsfaktorisering är också att bryta hemliga koder som är nummerbaserade.