Co wiem o liczbach pierwszych

Liczba pierwsza jest liczbą naturalną posiadającą dokładnie dwa różne podzielniki - 1 oraz samą siebie.
Wynika stąd, iż liczby 0 (nie dzieli się przez siebie) oraz 1 (ma tylko jeden podzielnik - samą siebie i nie jest on różny od 1) nie są liczbami pierwszymi. Oto kilka początkowych liczb pierwszych:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 ...

Twierdzenie: Liczb pierwszych jest nieskończenie wiele.

Dowód:
Twierdzenie to udowodnił sławny matematyk starożytnej Grecji, Euklides. Założył on, iż zbiór liczb pierwszych jest skończony i zawiera np. n liczb pierwszych:
p1, p2, p3, ..., pn
Następnie utworzył ich iloczyn powiększony o 1 zgodnie ze wzorem:
E = (p1 * p2 * p3 * ... * pn) + 1
Otrzymana liczba E nie jest podzielna przez żadną liczbę pierwszą ze zbioru liczb pierwszych, ponieważ każde takie dzielenie daje resztę 1. Zatem pozostają tylko dwie możliwości:
Liczba E jest nową liczbą pierwszą
Liczba E jest podzielna przez liczbę pierwszą nie zawartą w zbiorze liczb pierwszych.
W obu tych przypadkach otrzymujemy nową liczbę pierwszą, co przeczy twierdzeniu, iż zbiór zawierał wszystkie liczby pierwsze. Skoro tak, to nie może on być zbiorem skończonym. Jest to tzw. dowód przez sprowadzenie do sprzeczności.

Problem

Rozwiązanie 1

Liczba jest pierwsza (ang. prime), jeśli nie posiada dzielników(ang. divisors) innych poza 1 i sobą samą.

Pierwsze rozwiązanie testu na pierwszość (ang. primality test) polega na próbnym dzieleniu liczby p przez liczby z przedziału od 2 do [√p] i badaniu reszty z dzielenia. Powód takiego postępowania jest prosty – jeśli liczba p posiada czynnik większy od pierwiastka z p, to drugi czynnik musi być mniejszy od pierwiastka, aby ich iloczyn był równy p. W przeciwnym razie iloczyn dwóch liczb większych od √p dawałby liczbę większą od p. Zatem wystarczy przebadać podzielność p przez liczby z przedziału <2,[√p]>, aby wykluczyć liczby złożone.

Algorytm sprawdzania pierwszości liczby naturalnej

Wejście

Wyjście:

TAK, jeśli p jest pierwsze lub NIE w przypadku przeciwnym.

Elementy pomocnicze:

//  Metoda bisekcji      


#include <iostream>
#include <math.h>


//----------------------------


using namespace std;

int main()
{
  unsigned long long g,i,p;
  bool t;

  cin >> p;
  g = (unsigned long long)sqrt(p);
  t = true;
  for(i = 2; i <= g; i++)
  {
    if(p % i == 0)
    {
      t = false; break;
    }
  }
  if(t) cout << "TAK";
  else  cout << "NIE";
  cout << endl;
  return 0;
}