Rozkład liczby na czynniki pierwsze
Umiejętność rozłożenia liczby na czynniki pierwsze w C++ jest bardzo potrzebna, ponieważ jest to podproblem występujący w wielu innych zadaniach maturalnych. Jeżeli nie będziemy umieli dokonać takiego rozkładu, to mamy dużą szansę trafić na zadania, których nie będziemy mogli rozwiązać.
Spis treści
Rozkładanie liczby na czynniki pierwsze
Każda liczba naturalna, która jest większa od 1, składa się z liczb pierwszych oraz liczb złożonych.
Liczby naturalne – są to wszystkie liczby dodanie, całkowite (np. 1,2,3,4,5.. ) Składają się one z liczb pierwszych oraz liczb złożonych.
Liczby pierwsze to liczby, które posiadają dokładnie dwa dzielniki naturalne – 1 oraz samą siebie. Liczby złożone to liczby, które posiadają więcej niż dwa dzielniki. Przypominam, że dzielnikiem nazywamy taką liczbę całkowitą, która dzieli inną liczbę całkowitą bez reszty.
Z powyższego zdania można wyciągnąć proste wnioski: Jeżeli jakaś liczba naturalna nie jest liczbą pierwszą, tzn. że jest liczbą złożoną. Jeżeli jakaś liczba naturalna nie jest liczbą złożoną, tzn. że jest liczbą pierwszą.
Teraz trzeba przypomnieć jedno z twierdzeń matematyki o nazwie “Podstawowe twierdzenie arytmetyki”. Mówi ono, że każdą liczbę złożoną, można przedstawić w postaci iloczynu liczb pierwszych (stąd nazwa liczb złożonych).
Rozkład liczby N na czynniki pierwsze polega na odnalezieniu takich liczb pierwszych, których iloczyn (wynik mnożenia) wyniesie tyle co ta liczba N.
Jak jasno wynika z powyższych akapitów, rozkładać na czynniki pierwsze można tylko liczby złożone. Liczby pierwsze dzielą się tylko przez 1 i samą siebie, stąd nie da się ich rozłożyć. Oto przykładowe liczby:
Jak rozkładać na czynniki pierwsze
Rozkładanie liczby na czynniki pierwsze jest dość łatwe. Należy dzielić ją na jak najmniejsze liczby pierwsze aż dojdziemy do liczby 1. Jeżeli zaczynamy dzielić od 2 (najmniejsza liczba pierwsza) i nie da się dzielić bez reszty, wtedy próbujemy dla kolejnej liczby pierwszej aż znajdziemy taką, która dzieli bez reszty – czyli będzie dzielnikiem naturalnym. Przykładowo rozłóżmy liczbę 30 oraz 52:
Liczba 30 zapisana jako rozkład czynników pierwszych to \(2*3*5\), a liczba 52 to \(2*2*13\). Rozkład liczb na czynniki pierwsze naprawdę warto zapamiętać, bo wykorzystuje się go np. podczas obliczania NWD i NWW liczb.
Rozkład na czynniki pierwsze C++
Aby rozłożyć liczbę na czynniki pierwsze wystarczy nam pętla, w której będziemy po kolei sprawdzać, czy każda z liczb zaczynając od 2 dzieli docelową liczbę bez reszty. Nie zapomnij, ze liczby trzeba sprawdzać wielokrotnie (czynniki pierwsze mogą się powtarzać) więc są nam potrzebne dwie pętle:
#include <cstdlib>
#include <iostream>
using namespace std;
int main()
{
int liczba, pierwsza;
cout << "Podaj liczbe: ";
cin >> liczba;
pierwsza = 2;
while(liczba>1)
{
// sprawdz czy liczba dzieli sie bez reszty
while(liczba % pierwsza == 0)
{
cout << pierwsza << " ";
liczba = liczba / pierwsza; // podziel liczbe
}
pierwsza++; // sprawdz kolejna liczbe
}
system("PAUSE >NUL");
return 0;
}
Gdyby istniała potrzeba zapisu liczb pierwszych do tablicy bardzo łatwo możemy taką dodać do naszego kodu. Wtedy potrzebne jest także zwiększanie indeksu tablicy:
#include <cstdlib>
#include <iostream>
using namespace std;
int main()
{
int liczba, pierwsza, i;
int czynniki[999];
cout << "Podaj liczbe: ";
cin >> liczba;
i = 0;
pierwsza = 2;
while(liczba>1)
{
// sprawdz czy liczba dzieli sie bez reszty
while(liczba % pierwsza == 0)
{
czynniki[i] = pierwsza; // jezeli tak to zapisz czynnik pierwszy
liczba = liczba / pierwsza; // podziel liczbe
i++;
}
pierwsza++; // sprawdz kolejna liczbe
}
for (int j = 0; j < i; j++)
{
// wyswietl czynniki pierwsze
cout << czynniki[j] << " ";
}
system("PAUSE >NUL");
return 0;
}
