Algorytmy, C++, Matura z informatyki - nauka i materiały.

Rozkład liczby na czynniki

Zgodnie z podstawowym twierdzeniem arytmetyki:

„Każdą liczbę naturalną większą od 1, nie będącą liczbą pierwszą, można jednoznacznie przedstawić w postaci iloczynu liczb pierwszych.”


Oznacza to, że każdą liczbę możemy rozłożyć na czynniki, gdzie przez czynnik rozumiemy liczbę pierwszą, która dzieli daną liczbę bez reszty.
Np. 12=2x2x3, 78=2x3x13, a 286=2x11x13
Sugeruje nam to, że liczby pierwsze są pewnego rodzaju matematyczną interpretacją atomów – tworzą pozostałe liczby.

Tak przedstawia się schemat blokowy wykorzystanego przeze mnie algorytmu:

6 Comments on “Rozkład liczby na czynniki

    1. Taki zapis jest równoważny z zapisem a=a/i; Zmiennej a przypisujemy wartość równą ilorazowi a przez i.
      Dlaczego robimy coś takiego? Może wytłumaczę na przykładzie. Masz liczbę 28. W pierwszym kroku program sprawdza, czy 28 jest podzielne przez 2. Jest więc dzielimy 28 na dwa i w rezultacie otrzymujemy 14. 14 również jest podzielne przez 2, dzielimy i otrzymujemy 7. 7 już nie jest podzielne przez 2 dlatego i będzie rosło o 1 do momentu, aż znajdzie dzielnik siódemki. Dzielnikiem siódemki jest tylko 7, więc dzielimy 7 przez 7 i otrzymujemy 1. To już jest mniejsze od naszego warunku, dlatego kończymy wykonywanie pętli.

    2. Gdybyśmy nie dzielili liczby przez napotkany czynnik to wtedy mielibyśmy taką sytuację, że i w pętli for dojdzie do np. czwórki. 28 jest podzielne przez cztery, ale przecież nie jest liczbą pierwszą.
      W warunku natomiast napisałem a>= ponieważ dwójka jest najmniejszą z liczb pierwszych, a wykonując stopniowo to dzielenie, o które najpierw spytałeś a się zmniejsza. Dla 28 a przyjmuje wartości 28, potem 14, potem 7 i w końcu 1. Jedynka jest mniejsza od najmniejszej znanej liczby pierwszej, dlatego na pewno nie będzie miała czynnika, będącego liczbą pierwszą. Mam nadzieję, że trochę ci rozjaśniłem 🙂

Dodaj komentarz