Algoritmul factorului prim: C, Python Exemplu

Ce este o factorizare primă?

Factorul prim al unui număr este un factor care este el însuși un număr prim, divizibil doar cu 1 și cu sine însuși.

Exemplu: Factorii primi ai lui 10 sunt 2 și 5, deoarece 2 × 5 = 10.

Găsirea factorilor primi folosind iterație

Iterează de la 2 până la sqrt(n) și verifică divizibilitatea. În timp ce n este divizibil cu candidatul curent, împarte și afișează.

Exemplu: fiecare număr prim mai mare decât 40 se potrivește cu n²+n+41, deci n = 0, 1, 2 rezultă 41, 43, 47.

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

• Iterează numere de la 2 până la sqrt(n).
• Verificați modulul lui n pentru fiecare candidat; un rest zero înseamnă că respectivul candidat este factor prim.
• Adună fiecare număr prim care divide n.
• Rutina rulează în complexitate temporală 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 stochează cel mai mic factor prim al fiecărui număr până la o limită maximă, reducând drastic costul factorizării după precalculare.

• Înregistrați cel mai mic factor prim al fiecărui număr întreg până la limita maximă.
• Luați cel mai mic număr prim și adăugați-l la mulțimea factorilor.
• Împărțiți numărul la acel număr prim și repetați până ajunge la 1.
• Fiecare interogare rulează în aproximativ O(log n).

Exemplu: Un număr prim, altul decât 2 și 3, se încadrează în forma 6n-1 sau 6n+1. De exemplu, 5 = 6(1)-1 și 19 = 6(3)+1.

algoritm: definește un mulțime care stochează cel mai mic factor prim al fiecărui număr, folosind indicele ca valoare inițială pentru fiecare element.

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]

Articole pe aceeaşi temă

• Structura datelor grafice și Algorithms
• Problema vânzătorului călător
• Algoritmul metodei bisecției
• Algoritmul de sortare a găleților

Python Factori primi folosind iterația

Următoarele Python Codul găsește factorii primi folosind metoda iterativă de împărțire prin încercare:

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
2
2

Python Factori primi care folosesc recursiunea

Python Codul de mai jos folosește metoda sitului pentru a găsi factorii primi ai unui număr dat.

import math
High = (int)(1e5 + 7)
array = [0 for i in range(High)]

# generate smallest prime factors
def Sieve():
    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):  # divide until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n / array[n]))

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

Aceeași soluție iterativă scrisă în CIntroduceți un număr, apoi pentru fiecare candidat de la 2 până la sqrt(n), verificați divizibilitatea și afișați fiecare apariție a unui factor prim.

#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

Versiunea recursivă C oglindește Python Unu: construiți tabloul cu cei mai mici factori primi, apoi împărțiți recursiv la acel factor până când n ajunge la 1.

#include <stdio.h>
int Max = 100007;
int array[100007];

void Sieve()  // smallest prime factors up to Max
{
    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)  // divide until we reach 1
        return;
    printf("%d\n", array[n]);
    PrimeFactors(n / array[n]);
}

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

• Orice număr par, altul decât 2, poate fi scris ca suma a două numere prime (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• Nu există numere prime consecutive în afară de 2 și 3, deoarece 2 este singurul număr prim par.
• Fiecare număr prim, cu excepția 2 și 3, se încadrează în forma 6n + 1 sau 6n − 1, unde n este un număr întreg pozitiv.
• Mulțimea factorilor primi ai unui număr este unică.
• Numărul 1 nu este nici prim, nici compus.
• Factorizarea primă ajută la divizibilitate, simplificarea fracțiilor și găsirea numitorilor comuni.
• Factorizarea primă stă la baza codurilor criptografice bazate pe numere.

Întrebări frecvente