Czy liczba jest pierwsza?

Test pierwszości to algorytm określający, czy dana liczba jest pierwsza, czy złożona. Nie jest to równoważne znalezieniu jej rozkładu na czynniki pierwsze. W obecnej chwili nie są znane efektywne algorytmy rozkładu na czynniki pierwsze, natomiast testy pierwszości można przeprowadzać bardzo szybko.
 Metoda naiwna
Najprostszy test pierwszości wygląda następująco: dla danej liczby n należy sprawdzić, czy dzieli się ona kolejno przez 2, 3, aż do n−1. Jeśli przez żadną z nich się nie dzieli, oznacza to, że jest pierwsza.

Zamiast testować wszystkie liczby do n−1, wystarczy sprawdzić podzielność n przez liczby mniejsze lub równe sqrt(n).

Kolejne udoskonalenie polega na sprawdzaniu podzielności n jedynie przez liczby pierwsze mniejsze lub równe sqrt(n). Ich listę łatwo możemy uzyskać metodą sita Eratostenesa. Metoda ta wciąż wymaga wykonania dużej liczby (sqrt(n)) dzieleń, co oznacza, że już dla 50-cyfrowych liczb pierwszych jest niewykonalna na współczesnych komputerach

Lista kroków:

K01:g ← [√n]
K02:Dla i = 2,3,...,g wykonuj krok K03
K03: Jeśli n % i = 0, to pisz NIE i zakończ
K04:Pisz TAK
K05:Zakończ

Schemat blokowy

Program w C++

#include<iostream>

#include<cstdlib>

#include<cmath>

using namespace std;

bool czy_pierwsza(int n)

{

  if(n<2)

    return false;

 int g;

  g=sqrt(n);

  for(int i=2;i<=g;i++)

    if(n%i==0)

      return false; 

  return true;

}

int main()

{

  int n;

  cout<<"Podaj liczbe: ";

  cin>>n;

  if(czy_pierwsza(n))

    cout<<"Liczba "<<n<<" jest pierwsza"<<endl;

  else

    cout<<"Liczba "<<n<<" nie jest pierwsza"<<endl;

  return 0;

}

Rozwiązanie w Excel

W komórce E5 podajemy liczbę, której pierwszość chcemy zbadać.

Do komórki H5 należy wpisać formulę:

=JEŻELI(LUB(E5=2;E5=1);"Liczba pierwsza";JEŻELI(ORAZ(MOD(E5;WIERSZ(ADR.POŚR("2:"&ZAOKR.GÓRA(E5^0,5;0))))<>0);"Liczba pierwsza";"Liczba nie jest pierwsza"))

W komórce H5 pojawi się informacja czy liczba jest pierwsza.

Opracował: Maciej G.