Dzielniki liczby – implementacje

Ideą serii wpisów o podstawowych algorytmach jest podzielenie się z młodymi programistami (w tym przede wszystkim maturzystami) moimi implementacjami popularnych programów, wykorzystujących właśnie te algorytmy — w końcu nic tak nie szlifuje wiedzy, jak wykorzystanie jej w praktyce. Znajomość tych algorytmów jest istotna na maturze z informatyki, gdyż niektóre zadania zabraniają użycia wbudowanych metod. Przykładem jest algorytm sortowania — jesteśmy wtedy zmuszeni stworzyć go samodzielnie. Jednym z najbardziej podstawowych algorytmów jest ten, który z wyznacza dzielniki liczby naturalnej.

Za dzielnik liczby n uznajemy dowolną liczbę naturalną k, która dzieli liczbę n bez reszty. Dla przykładu dzielnikami liczby 24 są 1, 2, 3, 4, 6, 8, 12 i 24. Zauważ, że dla każdej liczby n ilość dzielników jest zawsze parzysta, a w nich zawsze znajdzie się 1 i n. Liczby, które posiadają jedynie dwa dzielniki: 1 i siebie samą, nazywamy liczbami pierwszymi, o których dowiesz się więcej tutaj. Jak znaleźć dzielniki liczby? Musimy najpierw ustalić algorytm, według którego będziemy działać, a następnie zaimplementujemy go w Javie, C++ i Pythonie.

Algorytm znajdowania dzielników liczby

Na początku musimy ustalić pewną liczbę naturalną n. Aby znaleźć jej wszystkie dzielniki, najprościej będzie sprawdzić po kolei reszty z dzielenia przez wszystkie liczby mniejsze lub równe jej połowie, wiadomo przecież, że dzielenie liczby przez więcej niż jej połowę nigdy nie da całkowitego wyniku. Do tej operacji wykorzystamy pętle oraz operator modulo (%), który zwraca resztę z dzielenia dwóch liczb. Na początku algorytmu wypisujemy 1 — jest to dzielnik każdej liczby. Następnie sprawdzamy wszystkie liczby z przedziału <2, (n/2)> za pomocą operatora modulo — jeżeli reszta z dzielenia będzie równa 0, wypisujemy iterowaną liczbę jako dzielnik. Na koniec algorytmu wypisujemy liczbę n — ona też jest swoim własnym dzielnikiem. Algorytm jest prosty w działaniu i nie pochłania wielu zasobów, a jego schemat blokowy możesz przeanalizować poniżej:

Schemat blokowy algorytmu znajdującego dzielniki liczby

Dzielniki liczby — implementacja Java, C++, Python

Jak już wspominałem na początku, znajomość podstawowych algorytmów jest wręcz wymagana na maturze z informatyki. Dobrze by było również wiedzieć jak je użyć w praktyce, dlatego, jak w każdym ze wpisów o algorytmach, poniżej umieszczam implementacje algorytmu. Ponieważ post ten kierowany jest głównie do osób przygotowujących się do matury, implementacje te napisane są w trzech dostępnych na maturze językach programowania: Javie, C++ i Pythonie.

Dzielniki liczby – implementacja C++

Dzielniki liczby – implementacja Python

Dzielniki liczby – implementacja Java

grupa wsparcia matura z informatyki
You Might Also Like
Dodaj komentarz

icon