Skip to content

Czy liczba jest liczbą pierwszą?

Posted in Nauka, and Programowanie

Na stronie Centralnej Komisji Egzaminacyjnej ( CKE ) możemy znaleźć wykaz algorytmów, których znajomość jest wymagana. Jednym z nich jest znajomość poprawnego zbadania, czy podana liczba jest liczbą pierwszą. Nie zwlekając dłużej przejdźmy do rozwiązania problemu.
Najpierw trochę teorii o poprawnym poszukiwaniu liczby pierwszej.

Liczba pierwsza to liczba, która dzieli się tylko przez 1 i samą siebie. Tego warunku nie spełnia liczba 1 i 0, z prostych przyczyn definicji liczby pierwszej, która dokładnie brzmi:

 

Liczby pierwsze to liczby naturalne, które posiadają dokładnie dwa dzielniki (liczbę 1 i samą siebie).

Aby wykazać, że liczba naturalna jest liczbą pierwszą musimy wykazać, że reszta z dzielenia liczby przez liczby mniejsze, bądź równe pierwiastkowi kwadratowemu liczby sprawdzanej jest różna od 0.
Wiem – brzmi to trochę zawile. Sam pisząc to powyżej dwa razy się zastanawiałem, czy poprawnie napisałem to co chciałem Ci powiedzieć. Niestety prościej się nie da, gdy nie chcesz pominąć wszystkich warunków do poprawnego wykonania zadania.

Rozwiązanie

Schemat krokowy

  1. Podaj liczbę naturalną n.
  2. Jeżeli liczba n<2 wypisz „To nie jest liczba pierwsza”
  3. w przeciwnym wypadku kontynuuj algorytm
  4. Rób dopóki i:=2 ; i *i<=n ; i+1
  5. Jeżeli n mod i = 0 wypisz „To nie jest liczba pierwsza”
  6. W przeciwnym wypadku
  7. Wypisz „To jest liczba pierwsza”
Algorytm w C++

One Comment

  1. […] których znajomość jest wymagana. Ostatnio pisałem na temat algorytmu, który sprawdza, czy dana liczba jest liczbą pierwszą. Wpis postanowiłem udostępnić na wykop.pl i zauważyłem, że wywołał on dyskusję, mimo że […]

    16 maja 2016
    |Reply

Dodaj komentarz

%d bloggers like this: