Question

Salutare , astazi am invatat la programare sa verificam daca un numar este prim , codul este acesta
int nr, i = 2, prim = 1;
cin >> nr;
while (i <= sqrt(nr)) {
if (nr%i == 0) {
prim = 0;
break;
}
i++;
}
if (prim == 1) {
cout << "Numarul este prim !";
}
else {
cout << "Numarul nu este prim !";
}


As vrea si eu sa stiu de ce orice numar neprim are cel putin un divizor mai mic sau egal cu radicalul numarului pe care vrem sa-l testam .
Care este gandirea matematica din spate ?

Answer 1

sunt 3 optiuni la repetitiva de verificare de numar prim

prima este sa verifici de la 2 la n; aceasta este cea mai putin eficienta din moment ce treci de cel mai mare divizor posibil al lui n (adica n/2), si nu mai are rost sa verifici daca 10 se imparte la 6 (de exemplu)

a doua optiune este sa te opresti la n/2, care, din nou, este cel mai mare divizor posibil, deci algoritmul ar avea sens

varianta cu sqrt(n) este optima pentru ca verifici cel mai mic numar de divizori. raspunsul simplu e ca daca numarul nu este prim atunci sigur va avea un divizor mai mic sau egal cu radicalul lui

verifica exemple gen 16, 21, 45 etc daca vrei sa te convingi, nu stiu sa iti explic exact