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

Liczby pierwsze – implementacja c++

Liczbami pierwszymi nazywamy takie liczby naturalne (n>1), których dzielnikami są jedynie jedynka i ona sama. Liczby pierwszej nie da się rozłożyć na więcej czynników niż 1 i n.

Do liczb pierwszych zaliczamy 2,3,5,7,11,13,17,19,23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71…

 

Ciekawostką dotyczącą liczb pierwszych jest fakt, że jak dotąd nie udało się znaleźć żadnego porządku w ich występowaniu. Liczby pierwsze ciągną się w nieskończoność z wrażeniem przypadkowości. Czasem liczby pierwsze występują gęsto, kiedy innym razem bardzo rzadko.

Badaniem liczb pierwszych zajmowali się m.in. Leonard Euler i Bernhard Riemann, którego twierdzenie jest uznawane za klucz do zrozumienia liczb pierwszych.

7 Comments on “Liczby pierwsze – implementacja c++

  1. 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.

    1. 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 🙂

  2. 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

    1. 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 😉

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *