Tutorial Algoritm Verificare Numar Prim In C++

[+Gabriel™]

Se verifica prin impartirea numarului repetat de la 2 la radical din acesta. Daca exista o impartire cu rest 0 (=impartire buna) inseamna ca numarul nu este prim.

#include<iostream>
#include<conio.h>
#include<math.h>
using namespace std;

int main() {
int ok=0, i, n;
cout<<"n= "; cin>>n;
for(i=2; i<=sqrt(n); i++)
if(n%i==0) ok=1;
if(ok) cout<<"Nu este prim.";
else cout<<"Este prim.";
_getch();
} 

[+Vlăduț Rădulescu]

Eu îl știu chiar mai ușor de atât:

#include<iostream.h>
int main()
{int i,n,s;
s=0;
cout<<"n=";
cin>>n;
for(i=1;i<=n;i++)
{if(n%i==0)
s=s+1;}
if(s==2)
cout<<"Numărul este prim"
else
cout<<"Numărul nu este prim"}

[Courage]

Si de ce vrei sa calculezi sqrt(n) de fiecare data cand incrementezi i?

#include <cmath>
bool prim(int numar)
{
    if (numar % 2 == 0 || numar < 3)
    {
        return numar == 2;
    }
    unsigned int sq_root = sqrt(numar);
    for (unsigned int diviz = 3; diviz <= sq_root; diviz += 2)
    {
        if (numar % diviz == 0)
        {
            return false;
        }
    }
    return true;
}

[+GodsOtherHand]

Nu cred ca se calculeaza sqrt(n) de fiecare data. Compilatorul ar trebui sa optimizeze chestia aia si sa se apeleze doar o data.

[Kid Koder]

Nu cred ca se calculeaza sqrt(n) de fiecare data. Compilatorul ar trebui sa optimizeze chestia aia si sa se apeleze doar o data.

 

Defapt se calculeaza de fiecare data sqrt(n), dar pentru ca sqrt-ul mai da rateuri uneori, era mai lejer asa:

for(int i = 2; i * i <= n; ++i) {
    ...
}