Un posibil algoritm pentru a rezolva eficient primalitatea unui număr poate fi asta :
bool prim(int x)
{
if (x < 2)
return false;
for (int d = 2; d <= sqrt(x) ; d++)
if (x % d == 0)
return false;
return true ;
}
Funcția are proprietatea de a parcurge posibilii divizori ai lui x într un timp mult mai scrurt decât prin metoda clasica pana la n / 2.
Complexitate O(sqrtn)
