Rozkład na czynniki pierwsze

Rozłożenie liczby na czynniki pierwsze polega na zapisaniu jej w postaci iloczynu liczb pierwszychliczba pierwszaliczb pierwszych (np. $46=2\cdot 23$). Już od starożytności wiadomo, że każda liczba naturalna większa niż jeden jest albo liczbą pierwszą, albo iloczynem liczb pierwszych (czyli tak zwaną liczbą złożonąliczba złożonaliczbą złożoną).

Metodę rozkładu liczby na czynniki pierwsze poznajemy już w szkole podstawowej, niedługo po opanowaniu tabliczki mnożenia. Jeśli chcesz przypomnieć sobie ten algorytm, zapoznaj się z e‑materiałem FaktoryzacjaPZeBttEDvFaktoryzacja.

Realizacja algorytmu w języku w C++

Napiszemy w języku C++ program rozkładający liczbę naturalną na czynniki pierwsze.

Specyfikacja problemu:

Dane:

• liczba – liczba do rozłożenia na czynniki pierwsze; liczba naturalna większa od 1

Wynik:

Program wypisuje wszystkie czynniki pierwsze liczby liczba w jednym wierszu, po przecinku.

Zaczniemy od zdefiniowania zmiennej typu int. Użyjemy jej do przechowania wartości liczby rozkładanej na czynniki.

int liczba = 24;

Następnie utworzymy pętlę for. Będzie ona działać aż do momentu, w którym zmienna liczba będzie równa 1. W pętli deklarujemy zmienną czynnik, która będzie oznaczała kolejne rozpatrywane przez nas potencjalne czynniki pierwsze. Będzie ona inkrementowana w każdej iteracji. Jej wartością początkową jest 2, ponieważ jest to najmniejsza liczba pierwsza.

for (int czynnik = 2; liczba > 1; ++czynnik) {

}

Wewnątrz pętli for umieścimy pętlę while. Pętla while wykonuje się, dopóki reszta z dzielenia zmiennej liczba przez czynnik wynosi 0 (czyli dopóki zmienna czynnik jest podzielnikiem rozkładanej liczby).

for (int czynnik = 2; liczba > 1; ++czynnik) {
	while (liczba % czynnik == 0) {
		cout << czynnik << ", ";
		liczba /= czynnik;
	}
}

Mamy zatem program, który rozłoży daną liczbę na czynniki pierwsze:

#include <iostream>

using namespace std;

int main() {
	int liczba = 24;
	
	for (int czynnik = 2; liczba > 1; ++czynnik) {
		while (liczba % czynnik == 0) {
			cout << czynnik << ", ";
			liczba /= czynnik;
		}
	}
}

Możemy jednak stworzyć bardziej optymalny algorytm. Zauważmy, że nie jest konieczne sprawdzanie wszystkich czynników, aż wartość liczba wyniesie 1.

Każda liczba złożona, ma maksymalnie jeden czynnik pierwszy większy od jej pierwiastka.

W związku z tą obserwacją, możemy przerwać iterację w momencie, gdy czynnik podniesiony do kwadratu będzie większy od wartości liczba. Na końcu wypiszemy wartość zmiennej liczba, jeżeli jest ona większa od 1.

#include <iostream>

using namespace std;

int main() {
	int liczba = 24;
    
	for (int czynnik = 2; czynnik * czynnik <= liczba; ++czynnik) {
		while (liczba % czynnik == 0) {
			cout << czynnik << ", ";
			liczba /= czynnik;
		}
	}
    
	if (liczba != 1) {
		cout << liczba;
	}
}

Słownik