Implementacja algorytmu w języku C++

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.

Przykład 1

Liczba 27, po rozkładzie na czynniki pierwsze, to 3⋅3⋅3. Żaden z czynników zatem nie jest większy od pierwiastka tej liczby, wynoszącego 5,196...

Przykład 2

Pierwiastek liczby 14 to 3,74..., a liczba ta po faktoryzacji to 2⋅7. Widzimy zatem, że tylko jeden czynnik pierwszy jest 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;
	}
}

Polecenie 1

Napisz program, który pobierze od użytkownika liczbę naturalną, a następnie wskaże rozkład podanej przez użytkownika liczby na czynniki pierwsze.

Specyfikacja problemu:

Dane:

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

Wynik:

Program wypisuje, na standardowe wyjście, wszystkie czynniki pierwsze liczby n oddzielone spacją.

R1apFvV7IMLGP

Polecenie 2

Porównaj swoje rozwiązanie z zaprezentowanym w filmie.

R17ANmE6L093q

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

R1a8XwRa8ekxK

Przycisk do pobrania pliku TXT z kodem źródłowym.

Plik TXT o rozmiarze 353.00 B w języku polskim

R1R2JUiZu0FgV

Przycisk do pobrania pliku TXT z kodem źródłowym.

Plik TXT o rozmiarze 476.00 B w języku polskim

Słownik

faktoryzacja

rozkład liczby na czynniki pierwsze, czyli zapisanie dowolnej liczby naturalnej większej od 1 za pomocą iloczynu liczb pierwszych

liczba pierwsza

liczba naturalna większa od 1, która ma tylko dwa dzielniki, dzieli się tylko przez 1 oraz przez samą siebie

liczba złożona

liczba naturalna większa od 1 będąca iloczynem liczb pierwszych

Wizualizacja działania algorytmu

Strefa wyzwań

Realizacja algorytmu w języku w C++

Słownik