Algorytm badania czy liczba jest pierwsza

Wstęp:

  • DEFINICJA. Liczba pierwsza to taka liczba naturalna, która ma dokładnie dwa dzielniki naturalne: jedynkę i samą siebie.
  • Aby określić czy liczba n jest pierwsza, należy sprawdzić jej dzielniki.
  • Nie musimy sprawdzać wszystkich dzielników w przedziale <2, n>.
  • Wystarczy sprawdzić czy dana liczba n ma dzielniki w przedziale <2, sqrt(n)>, gdzie sqrt-pierwiastek
  • Korzystając z poniższej ilustracji z dzielnikami dla przykładowych liczb, przeanalizuj dlaczego tak jest:
    podzielniki liczb

Film może pomóc:

Schemat algorytmu:

czy liczba pierwsza algorytm
Pobierz plik algorytmu dla programu Magiczne Bloczki

Liczby pierwsze do 100:

pierwsze d0 100

Przykładowy kod programu w C++ z wykorzystaniem funkcji opartej o iterację while:

Kody chwilowo są wyłączone - skorzystaj z filmu

Wykorzystanie kodu

  • Powyższy kod można wykorzystać w środowisku Dev C++ lub innym. Wystarczy utworzyć nowy projekt i wkleić ten kod zamiast istniejącego.
  • Można też użyć kodu na jednej ze stron WWW z kompilatorami on-line, na przykład na stronie: www.cpp.sh