Testam potentialii divizori ai unui numar pana la radicalul numarului. Daca numarul este prim, la un moment dat nu o sa se mai respecte conditia: d * d <= n. Daca numarul nu este prim, o sa pice aceasta conditie: n % d != 0.
Daca vrei, iti explic de ce este suficient sa mergem pana la radicalul numarului.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int d = 2;
while(d * d <= n && n % d != 0)
d++;
if(d * d > n && n > 1)
cout <<"Numarul este prim";
else
cout << "Numarul nu este prim";
return 0;
}
