Algoritmul factorului prim: C, Python Exemplu

Ce este o factorizare primă?

Factorul prim al unui dat Orice numărul este factorul care este a număr prim. Factorii atunci când sunt înmulțiți vă oferă un alt număr. Un număr prim este divizibil cu el însuși sau cu 1.

Cu alte cuvinte, factorii primi sunt determinați prin găsirea numerelor prime care se înmulțesc împreună pentru a forma numărul original.

Exemplu: Factorii primi ai lui 10 sunt 2 și 5. Acest lucru se datorează faptului că 2X5 =10 și ambele 2,5 sunt numere prime.

Găsirea factorilor primi folosind iterație

Pentru a găsi factorii primi ai unui număr dat, mai întâi repetăm ​​toate numerele de la 2 până la rădăcina pătrată a numărului, apoi verificăm dacă fiecare număr este prim. Atâta timp cât numărul original este împărțit la acest prim, continuăm să adăugăm acest prim cu fiecare iterație.

Exemplu:

Fiecare număr prim mai mare de 40 se scrie cu următoarea formulă: n²+n+41. Deci, putem înlocui n cu toate numerele pentru a găsi factorul prim corespunzător. de exemplu, 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,...

Cum se imprimă un factor prim al unui număr?

• În această metodă, vom repeta numerele de la 2 până la rădăcina pătrată a numărului, așa cum sa menționat în secțiunea anterioară.
• Pentru aceasta, trebuie să verificăm modulul numărului inițial pe fiecare dintre numerele de la 2 până la rădăcina pătrată a lui n .
• Apoi, găsim lista numerelor prime care sunt factori ai lui n.
• Această soluție este în complexitatea de timp O(Sqrt(n)).

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

Algoritmul Sieve

Metoda Sieve se bazează pe stocarea celui mai mic factor prim al numerelor, ceea ce reduce semnificativ complexitatea atunci când se calculează factorii primi pentru orice număr. Algoritmul Sieve găsește toți factorii primi oarecum eficient.

• Conceptul principal al acestui algoritm este de a stoca cel mai mic factor prim al fiecărui număr până la numărul maxim.
• Luăm cel mai mic prim pentru fiecare număr dat și îl adăugăm la setul de factori primi.
• În cele din urmă, împărțim la acest număr prim și repetăm ​​acești pași până ajungem la 1.
• Toate acestea se realizează în complexitatea timpului O(log(n)), îmbunătățind foarte mult eficiența soluției.
• Ceea ce face posibilă calcularea factorilor primi ai unor numere mult mai mari decât cei cu care am fi putut să ne ocupăm folosind abordarea anterioară.

Exemplu:

A doua modalitate este de a verifica dacă numărul poate fi scris ca 6n-1 sau 6n+1, deoarece orice număr prim, altul decât 2 și 3, ar trebui scris în una dintre cele două formule. de exemplu, 5=6(1)-1, 19=6(3)+1,... .

algoritm:

Definiți o matrice pentru a stoca cel mai mic factor prim al fiecărui număr cu valoarea indexului ca valoare inițială pentru fiecare element al mulțime.

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 Factori primi folosind iterația

Aici, vom afișa un cod în Python limbaj pentru a găsi factorii primi ai unui număr dat într-o metodă iterativă:

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)

ieșire:

Enter the number you want: 4
4

Python Factori primi care folosesc recursiunea

Această secțiune arată un cod în Python limbă folosind metoda sită pentru a găsi factorii primi ai unui număr dat.

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)

ieșire:

Enter the number you want: 4
2
2

Programul de factori primi C folosind iterația

Este aceeași soluție ca cea iterativă python, dar scrisă în Limbajul C.

Cerem utilizatorului să introducă numărul, apoi pentru fiecare număr de la 2 la rădăcina pătrată a acestui număr, trebuie să verificăm dacă este divizibil prin imprimarea tuturor aparițiilor acestui factor.

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

ieșire:

Enter the number you want: 2
2

C Programul de factori primi care utilizează recursiunea

Aceasta este aceeași soluție ca cea recursivă python, dar scrisă în C.

Putem cere utilizatorului să introducă numărul; apoi, construim tabloul de numere prime care stochează cel mai mic factor prim al fiecărui număr. În cele din urmă, numim funcția recursivă Factori primi, care împarte numărul dat la cel mai mic factor prim al său și se reamintește până când ajunge la unu.

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

ieșire:

Enter the number you want: 2
2

Câteva fapte interesante despre numerele prime

• Unul dintre cele mai interesante fapte este că orice număr par, altul decât 2, poate fi suma a două numere prime.
• De exemplu: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … etc.
• Un alt fapt este că nu există numere prime consecutive, altele decât 2 și 3, deoarece singurul număr prim par este numărul 2.
• De asemenea, toate numerele prime, cu excepția lui 2 și 3, pot fi scrise sub următoarea formă: 6 * n + 1 sau 6 * n – 1, unde n este un număr întreg pozitiv.
• Setul de factori primi ai unui număr este unul unic.
• Numărul 1 nu este nici prim, nici compus.
• Descompunerea în factori primi a numerelor poate ajuta la rezolvarea unor probleme precum divizibilitatea, simplificarea fracțiilor și găsirea numitorilor comuni ai diferitelor fracții.
• De asemenea, una dintre utilizările interesante ale factorizării prime este ruperea codurilor secrete care se bazează pe numere.