Jakub Piskorowski on 30/08/2023 wersja: 1.0
Przedstawienie działania algorytmu rozkładu liczb na czynniki pierwsze.
Kod źródłowy:
📒 Poziom 2
Powrót do Algorytmika
Zacznijmy od definicji. Rozkład liczby naturalnej n>1 na czynniki pierwsze polega na przedstawieniu jej w postaci iloczynu liczb pierwszych.
Liczby złożone będą miały co najmniej dwa czynniki pierwsze. Liczby pierwsze się nie rozkładają. Problem rozwiążemy sposobem szkolnym. Popatrzmy najpierw na kilka przykładów. Rozłóżmy liczby 24, 100, 1520:
24 = 2 * 2 * 2 * 3
100 = 2 * 2 * 5 * 5
1520 = 2 * 2 * 2 * 2 * 5 * 19
Liczbę do rozłożenia będziemy dzielić przez liczby pierwsze tak długo, aż z liczby rozkładanej zrobi się 1.
Rozpoczynamy od dwójki - jest to pierwsza liczba pierwsza. Jeśli rozkładana liczba dzieli się bez reszty przez 2, to wypisujemy 2 i skracamy ją przez 2. Czynność powtarzamy tak długo, jak długo liczba dana liczba jest podzielna przez 2. W drugim kroku szukamy następnego dzielnika rozkładanej liczby. Będzie to następna liczba pierwsza. Czynności te powtarzamy do momentu uzyskania wartości 1.
Zakładamy, że liczba, która znajdzie się na wejściu będzie większa od jedynki.
Wejście:
n – liczba naturalna podana przez użytkownika
k - liczby pierwsze
Lista kroków:
K1: k ← 2 Ustawiamy k na pierwszą liczbę pierwszą
K2: dopóki n > 1 rozkład liczby na czynniki pierwsze
wykonuj kroki k3...k6
K3: dopóki n modulo k = 0 dopóki liczba jest podzielna przez k
wykonuj kroki K4...K5
K4: wyświetl k
K5: n ← n / k
k6: k ← k + 1
Wynik działania programu:
Podaj liczbe: 1520
Czynniki pierwsze liczby 1520: 2 2 2 2 5 19
Kod źródłowy: rozklad-liczby.cpp