Rozkład na czynniki pierwsze (Faktoryzacja)

Zgodnie z podstawowym twierdzeniem arytmetyki, każdą liczbę złożoną można przedstawić w postaci iloczynu liczb pierwszych. Ten proces nazywamy rozkładem na czynniki pierwsze lub faktoryzacją.

Na przykład:

• 12 = 2 * 2 * 3
• 100 = 2 * 2 * 5 * 5
• 13 = 13 (liczba pierwsza ma tylko jeden czynnik – samą siebie)

Rozkład przydaje się w wielu zadaniach maturalnych, do znajdowania NWD/NWW w pamięci, upraszczania ułamków i łamania prostych szyfrów.

Jak działa algorytm?

Sposób działania jest bardzo naturalny – przypomina ręczne dzielenie kreską na lekcjach matematyki.

1. Zaczynamy od najmniejszej możliwej liczby pierwszej: i = 2.
2. Dopóki nasza liczba n dzieli się przez i bez reszty:
   • Wypisujemy i (znaleźliśmy czynnik!).
   • Dzielimy n przez i i przypisujemy wynik z powrotem do n.
3. Jeśli n nie dzieli się już przez i, to zwiększamy i o 1 (czyli sprawdzamy kolejną potencjalną liczbę pierwszą).
4. Pętlę przerywamy, gdy sprawdziliśmy już dzielniki do pierwiastka z n. Jeśli na sam koniec n jest większe od 1, oznacza to, że ostatnim, największym czynnikiem jest samo pozostałe n (np. przypadek liczby pierwszej).

Dzięki zastosowaniu sprawdzania tylko do pierwiastka z n (identycznie jak w algorytmie na sprawdzanie liczby pierwszej), osiągamy świetną złożoność O(√n).

Kod Algorytmu

Python

def rozklad(n):
    czynniki = []
    i = 2
    
    # Sprawdzamy dzielniki do pierwiastka z n
    while i * i <= n:
        # Dopóki n dzieli się przez i, to 'i' jest naszym czynnikiem
        while n % i == 0:
            czynniki.append(i)  # Zapisujemy czynnik
            n = n // i          # Dzielimy n przez i
        i += 1
        
    # Jeśli na końcu zostało nam n większe od 1,
    # to jest to ostatni czynnik (liczba pierwsza).
    if n > 1:
        czynniki.append(n)
        
    return czynniki

# Testowanie
print(f"Czynniki 100: {rozklad(100)}")
print(f"Czynniki 13: {rozklad(13)}")

C++

#include <iostream>
using namespace std;

void rozklad(int n) {
    cout << "Czynniki liczby " << n << ": ";
    
    int i = 2;
    // Sprawdzamy dzielniki do pierwiastka
    while (i * i <= n) {
        while (n % i == 0) {
            cout << i << " ";
            n = n / i;
        }
        i++;
    }
    
    // Jeśli z liczby zostało coś większego niż 1, wypisujemy
    if (n > 1) {
        cout << n << " ";
    }
    cout << endl;
}

int main() {
    rozklad(100);
    rozklad(13);
    return 0;
}

[!TIP] Dla dociekliwych: Gdzie omijanie liczb złożonych? Może zastanawiać Cię, dlaczego zwiększając w pętli i o 1 (czyli i++), sprawdzamy po drodze liczby takie jak 4, 6 czy 8. Przecież czynniki mają być pierwsze! Otóż algorytm automatycznie się przed tym zabezpiecza. Zanim i osiągnie wartość 4, my już całkowicie i do oporu podzieliliśmy naszą liczbę n przez 2 w pętli while. Więc kiedy i=4, to n na sto procent przez 4 się już nie podzieli! Kod sam "omija" działanie dla liczb złożonych, bo ich czynniki pierwsze zostały wyciągnięte z n już wcześniej.