Liczby pierwsze – omówienie i implementacje

Operacje na liczbach są jedną z podstawowych rzeczy, z jakimi możemy spotkać się w informatyce. W końcu każdy typ zmiennej jest przechowywany w pamięci jako ciąg zer i jedynek. Nic dziwnego więc, że na maturze z informatyki często pojawiają się zadania związane z liczbami i ich właściwościami — najczęściej ze zbioru liczb naturalnych. Ciekawymi przypadkami liczb naturalnych są liczby pierwsze.

Algorytm to podstawa

Aby dowiedzieć się, czy liczba n jest liczbą pierwszą, musimy stworzyć odpowiedni algorytm. Sprawdzimy najpierw, czy n jest większa od dwójki — jak wiemy z definicji liczby 0 oraz 1 nie są liczbami pierwszymi, więc od razu je wykluczamy. Następnie, korzystając z pętli, sprawdzimy wszystkie liczby mniejsze lub równe pierwiastkowi z liczby n, zaczynając od dwójki. Można by oczywiście iterować poprzez wszystkie liczby do n—1 lub n/2, jednakże sposób z pierwiastkiem jest wydajniejszy.

Do sprawdzania podzielności wykorzystamy operator modulo (%) — zwraca on resztę z dzielenia dwóch liczb. Jeżeli którakolwiek liczba z tego przedziału będzie dzielnikiem liczby n (reszta z dzielenia będzie równa 0), to zwracamy od razu FAŁSZ — nie ma potrzeby sprawdzać podzielności przez 1 i n, gdyż dobrze wiemy, że niezależnie od n zawsze będą one jej dzielnikami. Jeżeli jednak w wyniku iteracji nie znajdziemy żadnego dzielnika, oznacza to, że tylko te dwie liczby — 1 i n — są jej dzielnikami, więc jest ona liczbą pierwszą — zwracamy wtedy PRAWDĘ. Cały algorytm przedstawiłem na schemacie blokowym poniżej:

liczby pierwsze implementacja

Liczby pierwsze — implementacja C++, Java, Python

Skoro mamy już algorytm, to pora go zastosować w wybranym języku. Na maturze z informatyki możesz wybrać jeden z trzech języków programowania, dlatego poniżej znajdziesz implementację w każdym z nich. Zwróć uwagę, że w C++ wykorzystaliśmy bibliotekę math.h, w Pythonie import math, zaś w Javie skorzystałem ze statycznej metody z klasy Math — wszystko to potrzebne, aby obliczyć pierwiastek kwadratowy (sqrt, z ang. square root) z liczby n.



Jeżeli chcesz poszerzyć swoją wiedzę na temat algorytmów, koniecznie sprawdź tę pozycję

Liczby pierwsze – implementacja C++

Liczby pierwsze – implementacja Java

Liczby pierwsze – implementacja Python

Liczby pierwsze — ciekawostki

  • Liczb pierwszych jest nieskończenie wiele
  • Do tej pory nikt nie wyznaczył wzoru funkcji, która dla dowolnego argumentu zwróci liczbę pierwszą.
  • Liczby pierwsze występują, wydawać by się mogło, w sposób losowy — raz gęściej, raz rzadziej.
  • Badaniem liczb pierwszych zajmowali się m.in. Leonard Euler i Bernhard Riemann, którego twierdzenie jest uznawane za klucz do zrozumienia liczb pierwszych.
  • Istnieje algorytm, który znajdzie wszystkie liczby pierwsze z przedziału <2, n> dla n należącego do liczb naturalnych — jest to tzw. sito Eratostenesa, któremu poświęciłem oddzielny artykuł o tutaj.
  • Istnieje również algorytm rozkładu dowolnej liczby naturalnej na liczby pierwsze, który opisałem w tym artykule.

Na koniec warto dodać, że powyższy algorytm, jest jednym z wielu wymaganych przez CKE algorytmów na maturze z informatyki. Jeżeli więc pragniesz się do niej jak najlepiej przygotować, gorąco polecam Ci przeczytać ten post. Dowiesz się w nim na co należy zwrócić szczególną uwagę przy nauce, a także znajdziesz tam listę najważniejszych algorytmów, które mogą przytrafić się na egzaminie.

grupa wsparcia matura z informatyki
You Might Also Like
8 komentarzy
  • Avatar photo
    Jednooki
    says:

    Nie do końca zrozumiałem powyższy kod i z innego źródła wziąłem trochę kodu i skleiłem coś takiego(zdjęcie kodu w załączniku). Jeśli nikomu to nie będzie przeszkadzało proszę o wytłumaczenie jak działa pętla for w napisanej funkcji.

    Jeśli dobrze rozumiem. Dla przykładu zadeklarowaną przez użytkownika liczbą będzie 5(int n). Petlą wykonuje się następująco. Ona zaczyna pracować od 2, ponieważ jest to najmniejsza liczba pierwsza oraz będzie się wykonywać do jej kwadratu jeśli dobrze rozumiem z jej zapisu.
    W instrukcji tej pętli mamy „n mod i” == 0. Czyli jeśli pętla zaczyna pracować przy podanym wyżej przykładzie to zaczyna dzielić podaną 5 przez 2 i zwraca nam prawdę ponieważ mamy resztę z dzielenia.

    Chyba dobrze to rozumiem?

    Jeszcze chcę się dowiedzieć, ponieważ w tej pętli mamy inkrementacje „i++”, która będzie nam zwiększała zmienną i po pozytywnym wykonaniu pętli. I chciałbym żeby ktoś mi to zobrazował w jaki to sposób działa jeśli przechodzi nam liczba początkowa i=2 na np. 3, ponieważ nie mogę sobie tego jakoś wyobrazić. Chyba że po prostu tak się nie będzie dało ponieważ to szuka nam czy liczba jest podzielna i jak nie jest zwraca nam prawdę…
    https://uploads.disquscdn.com/images/fc2099ea7427f577783cbf1800fc764c55c765df65ed18b800362e9c15e560e8.png
    Mam nadzieję, że ktoś zrozumie to co napisałem :DDD

    • Avatar photo
      Łukasz Kosiński
      says:

      Własnie nie mój drogi. Warunek 5%2==0 nie zwróci nam prawdy, gdyż wynikiem działania 5 mod 2 jest jeden (reszta z dzielenia dwójki przez pięć to właśnie jedynka), a jeden jest różne od zera, więc mamy fałsz także instrukcja return się nie wywoła.

      Dla takiej na przykład piątki funkcja sprawdzi najpierw, czy pięć jest podzielne przez dwa. Nie jest więc przejdzie do następnego kroku zwiększając przy okazji i (i++). Teraz „i” wynosi 3, ale i*i, czyli 3*3 jest większe od naszego n, czyli pięć także pętla kończy swoje działanie.

      Zadaniem funkcji sprawdz_czy_pierwsza jest sprawdzenie, czy liczba jest podzielna przez jakąkolwiek liczbę (poza jedynką i nią samą).
      Gdybyś tak miał na przykład sprawdzić, czy 25 jest liczbą pierwszą to funkcja działa tak… Najpierw sprawdza, czy 25 jest mniejsze od dwóch nie jest więc lecimy dalej. Zaczyna działać pętla. W pierwszej iteracji sprawdza, czy 25 jest podzielne przez 2. Nie jest więc zwiększamy i o 1 i sprawdzamy, czy 25 jest podzielne przez 3. Nie jest, więc znowu zwiększamy o 1. Mamy 4, które również dzieli 25 z resztą. Zwiększamy „i” o jeden, wynosi więc teraz 5. Sprawdzamy, czy jeszcze mieścimy się w warunku. 5*5=25, czyli warunek w pętli spełniony. Sprawdzamy, czy co powie nam if. 25%5==0 (?) TAK, ponieważ resztą z dzielenia 25 przez 5 jest 0. Także wykona nam się instrukcja return, która zwróci oczywiście fałsz -> liczba nie jest pierwsza.
      Taka rada ode mnie. Zawsze, gdy nie rozumiesz dlaczego coś nie działa (albo działa) sprawdź sobie działania pętli tak jakby krok po kroku. Wybierz sobie jakąś liczbę i wyobraź sobie jak wyglądałoby wykonanie funkcji dla niej.
      Pozdrawiam 😉

  • Avatar photo
    Gumix 69 here
    says:

    Przydało by się kilka wersji programu żeby młodego programisty nie wpędzać od razu na morze rekurencji i do zatok wskaźników.

    • Avatar photo
      adminkozaczek
      says:

      Wychodzę z założenia, że kursów programowania w internecie jest mnóstwo, dlatego nie chcę pisac żadnych tutoriali jak. Przedstawiam tylko możliwie optymalne rozwiązania., ale faktycznie może iteracyjna wersja też by się przydała 🙂

Dodaj komentarz

icon