Rozkład liczb na czynniki pierwsze - teoria

Algorytm rozkładu liczby na czynniki pierwsze służy do znalezienia wszystkich czynników pierwszych liczby n. Proces ten polega na kolejnych próbach dzielenia liczby przez najmniejsze liczby pierwsze i eliminacji znalezionych czynników.

Kluczowa idea

Algorytm zaczyna od liczby 2, która jest najmniejszą liczbą pierwszą. Sprawdza, czy liczba n jest podzielna przez 2. Jeśli tak, dzieli ją przez 2 i powtarza ten proces, dopóki liczba nie będzie już podzielna przez 2. Następnie przechodzi do kolejnych liczb, zwiększając krokowo dzielnik i sprawdza podzielność przez liczby 3, 4, 5 itd., aż n zostanie zredukowane do 1.

Przykład działania

Rozważmy rozkład liczby 60:

• Krok 1: 60 dzieli się przez 2 (liczba pierwsza), dzielimy 60 przez 2, otrzymujemy 30. Zapisujemy 2.

• Krok 2: 30 dzieli się przez 2, dzielimy 30 przez 2, otrzymujemy 15. Zapisujemy 2.

• Krok 3: 15 nie dzieli się przez 2, przechodzimy do kolejnej liczby pierwszej – 3.

• Krok 4: 15 dzieli się przez 3, dzielimy 15 przez 3, otrzymujemy 5. Zapisujemy 3.

• Krok 5: 5 dzieli się przez 5 (liczba pierwsza), dzielimy 5 przez 5, otrzymujemy 1. Zapisujemy 5.

Wynik: Rozkład liczby 60 to 60= 2 × 2 × 3 × 5.

Zalety algorytmu:

• Jest fundamentalny w teorii liczb oraz w kryptografii, gdzie rozkład na czynniki pierwsze dużych liczb jest kluczowym problemem.

• Można go stosować dla liczb dowolnej wielkości, a jego optymalizacja polega na ograniczeniu liczby dzielników, które należy sprawdzić (np. testując tylko liczby pierwsze).

• Algorytm jest łatwy do zaimplementowania i wykorzystywany w wielu systemach numerycznych.

Rozkład liczb na czynniki pierwsze jest szczególnie przydatny w problemach związanych z szyfrowaniem, takich jak RSA, gdzie bezpieczeństwo zależy od trudności rozkładu bardzo dużych liczb.

Pseudokod - rozkład liczb na czynniki pierwsze

Algorytm rozkładu liczby na czynniki pierwsze polega na kolejnych próbach dzielenia liczby przez liczby naturalne, zaczynając od najmniejszej liczby pierwszej (2). Jeśli liczba jest podzielna przez daną liczbę, dzielnik jest wypisywany, a liczba jest dzielona przez ten dzielnik, dopóki nie przestanie być podzielna. Proces jest powtarzany dla kolejnych liczb, aż liczba zostanie zredukowana do 1.

Algorytm rozkładu liczby na czynniki pierwsze

Wejście:

• n - liczba, którą chcemy rozłożyć na czynniki pierwsze.

Wyjście:

• Wyświetl czynniki pierwsze liczby n.

Zmienne pomocnicze:

• k - potencjalny dzielnik liczby n, początkowo ustawiony na wartość 2.

Lista kroków:

K1:   Wprowadź liczbę n.
K2:   Ustaw k = 2   (Inicjalizacja dzielnika na pierwszą liczbę pierwszą).
K3:   Dopóki n > 1, wykonuj kroki K4-K6:
K4:       Dopóki n % k == 0:
          1. Wyświetl k   (Dzielnik znaleziony).
          2. Podziel n = n / k.
K5:       Zwiększ k o 1.
K6:   Zakończ.

Wynik działania programu:

Podaj liczbe: 60
Czynniki pierwsze liczby 60: 2 2 3 5