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.
Optymalizacja
Zamiast testować wszystkie liczby do n−1, wystarczy sprawdzić podzielność n przez liczby mniejsze lub równe sqrt(n).
Lista kroków
Specyfikacja algorytmu
Wejście:
n – liczba naturalna badana na pierwszość, n > 1
Wyjście:
TAK, jeśli n jest pierwsze lub NIE w przypadku przeciwnym.
Elementy pomocnicze:
g – granica sprawdzania podzielności p, g należy do N
i – kolejne podzielniki liczby n, i należy do N
K01 g ← [√n]
K02 Dla i = 2,3,...,g wykonuj krok K03
K03 Jeśli n % i = 0, to Wypisz "NIE" i zakończ
K04 Wypisz "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;
int i;
g=sqrt(n); // sqrt - pierwiastek kwadratowy
for (i=2;i<=g;i++)
if (n%i==0) return false;
return true;
}
int main()
{
int n; // sprawdzana liczba
cout<<"Podaj liczbe: ";
cin>>n;
if (czy_pierwsza(n)) //lub czy_pierwsza(n)==1
cout<<"Liczba "<<n<<" jest pierwsza"<<endl;
else
cout<<"Liczba "<<n<<" nie jest pierwsza"<<endl;
return 0;
}
