Rozkład liczby na czynniki

Arytmetyka to jeden z najstarszych i najlepiej poznanych przez ludzkość działów matematyki. Opisuje ona zasady podstawowych działań i operacji na liczbach, w związku z czym każdy z nas ma z nią do czynienia praktycznie na co dzień. Arytmetyka odgrywa również ważną rolę w informatyce. Jednym z algorytmów wymagających użycia jej podstawowych praw jest rozkład liczby na czynniki, któremu dzisiaj przyjrzymy się dokładniej.

 Rozkład liczby na czynniki to inaczej wypisanie wszystkich liczb pierwszych, których iloczyn da nam początkową liczbę. O tym, czym jest liczba pierwsza i jak sprawdzić, czy dowolna liczba n nią jest, przeczytasz dokładniej tutaj. Jak wspominałem w załączonym artykule — każdą liczbę naturalną większą niż 1 można rozłożyć na czynniki pierwsze. Jak rozłożyć dowolną liczbę na czynniki pierwsze? Poniżej  znajdziesz odpowiedź na to pytanie, a także implementacje w dostępnych na maturze językach: Java, C++ i Python.

 

Algorytm rozkładu na czynniki

Zanim przejdziemy do faktycznego tworzenia programu, musimy najpierw ustalić algorytm, według którego będzie on działać. Na początku pobieramy liczbę naturalną n od użytkownika. Następnie tworzymy pętlę, w której ustawiamy zmienną iterującą i na 2 (najmniejsza liczba pierwsza, od niej musimy rozpocząć) i sprawdzamy co krok, czy zmienna n jest większa lub równa 2 — 0 i 1 w wyniku dzielenia nie dadzą liczby pierwszej, więc je pomijamy. Następnie co iterację sprawdzamy, czy n jest podzielna przez i (reszta z dzielenia równa 0). Jeżeli tak, to dzielimy n przez i, wypisujemy jej czynnik i, a potem powtarzamy tą procedurę aż do momentu, w którym n nie będzie podzielne przez i. Następnie w tym samym kroku iteracji zwiększamy zmienną iteracyjną o 1. Dzięki temu liczba n będzie sukcesywnie zmniejszana w wyniku dzielenia przez jej czynniki, co doprowadzi do końca pętli. Jako że wypisaliśmy wszystkie czynniki liczby n, jednocześnie pomijając jedynkę, musimy ją również na koniec algorytmu wypisać. Do sprawdzania podzielności liczb w większości języków programowania można wykorzystać operator % (modulo) — jeżeli a % b jest równe zero, to oznacza, że a jest podzielna przez b. Przebieg algorytmu przestawiłem na schemacie blokowym poniżej:

Rozkład liczby na czynniki — implementacja C++, Java, Python

Mamy już zasadę działania naszego programu — pora na (najbardziej) przyjemny etap życia programisty — implementację. Decydując się na maturę z informatyki do wyboru masz jeden z trzech języków programowania: Javę, C++ lub Pythona. W związku z tym postanowiłem przygotować implementację w każdym z tych języków. W implementacjach zamieściłem także komentarze, abyś mógł lepiej zrozumieć, co się w nich dzieje.

 

Pamiętaj, że rozkład liczby na czynniki jest tylko jednym z wielu wymaganych algorytmów na maturze z informatyki. Jeżeli przygotowujesz się do niej i chcesz to zrobić jak najlepiej, zachęcam cię do zapoznania się z poradami, które zamieściłem w tym poście. Znajdziesz tam również listę najważniejszych algorytmów i odnośniki do ich implementacji.

grupa wsparcia matura z informatyki
You Might Also Like
7 komentarzy
  • Pingback: Sito Eratostenesa
    • Łukasz Kosiński
      says:

      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.

    • Łukasz Kosiński
      says:

      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

icon