[C++]Algoritm pentru verificarea unui numar prim

[~Wolf~]

Algoritm pentru verificarea primalitatii unui numar intreg.

Varianta eficienta din punct de vedere al timpului de executie
#include <iostream>
using namespace std;
unsigned int numar,divizor,prim=1;
int main()
{
cin>>numar;
if(numar<=1)
prim=0;
if(numar==2)
prim=1;
if(numar%2==0 && numar!=2)
prim=0;
for(divizor=2;divizor*divizor<=numar;divizor++)
if(numar%divizor==0)
{
prim=0;
break;
}
if(prim==1)
cout<<"Numarul "<<numar<<" este prim";
else
cout<<"Numarul "<<numar<<" nu este prim";
return 0;
}


Variante ineficiente
#include <iostream>
using namespace std;
unsigned int numar,divizor,numar_divizori,prim=1;
int main()
{
cin>>numar;
for(divizor=1;divizor<=numar;divizor++)
if(numar%divizor==0)
numar_divizori++;
if(numar_divizori==2) // adica doar 1 si el insusi
cout<<"Numarul "<<numar<<" este prim";
else
cout<<"Numarul "<<numar<<" nu este prim";
return 0;
}


*acest program nu este eficient deoarece parcurgem fiecare numar de la 1 pana la numarul citit intrucat sa gasim toti divizorii sai,lucru care dureaza mai mult decat in cazul in care luam doar numerele impare(exemplul 1)

Pentru eventualele greseli va rog lasati reply.