De ce contează?
Un număr prim este ca o cărămidă: nu poți să-l spargi în factori mai mici fără rest. Toate celelalte numere se construiesc din aceste cărămizi — de aceea numerele prime sunt „atomii" matematicii. Verificarea primalității apare în jumătate din problemele de matematică de concurs.
Definiție
Un număr natural n > 1 este prim dacă are exact 2 divizori: 1 și el însuși.
| Număr | Divizori | Prim? |
|---|---|---|
| 2 | 1, 2 | ✓ |
| 3 | 1, 3 | ✓ |
| 4 | 1, 2, 4 | ✗ |
| 7 | 1, 7 | ✓ |
| 12 | 1, 2, 3, 4, 6, 12 | ✗ |
Notează: 1 nu este prim (are un singur divizor), iar 2 este prim (singurul număr prim par).
Algoritmul eficient — O(√n)
Dacă n are un divizor d cu 1 < d < n, atunci fie d ≤ √n, fie n/d ≤ √n. E suficient să verificăm până la √n — dacă nu găsim niciun divizor acolo, n este prim:
bool estePrim(int n) {
if (n < 2) return false; // 0 si 1 nu sunt prime
for (int d = 2; d * d <= n; d++) {
if (n % d == 0) return false; // gasit divizor => nu e prim
}
return true;
}Implementare C++ — complet
#include <iostream>
using namespace std;
bool estePrim(int n) {
if (n < 2) return false;
for (int d = 2; d * d <= n; d++) {
if (n % d == 0) return false;
}
return true;
}
int main() {
int n;
cin >> n;
if (estePrim(n))
cout << n << " este prim" << endl;
else
cout << n << " nu este prim" << endl;
return 0;
}Exemple: 7 → prim, 12 → nu prim, 1 → nu prim, 2 → prim
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Verificare primalitate | O(√n) | O(1) |
| Variantă naivă (d până la n) | O(n) | O(1) |
Dacă trebuie să verifici primalitatea pentru toate numerele până la ~10⁶, folosește Ciurul lui Eratostene (studiat în clasa a 6-a) — precalculezi totul în O(n log log n). Funcția de mai sus este potrivită pentru numere individuale.
Vizualizare
Urmărește cum ciurul taie pe rând multiplii fiecărui număr prim, lăsând în picioare doar numerele prime:
Greșeala 1: Nu tratezi cazurile n < 2. Fără if (n < 2) return false, funcția returnează true pentru 0 și 1 — greșit prin definiție.
Greșeala 2: Verifici divizori până la n în loc de √n. De sute sau mii de ori mai lent pentru n mare.
Greșeala 3: Crezi că 2 nu e prim (este — singurul număr prim par) sau că 1 e prim (nu este — are un singur divizor, nu doi).
Greșeala 4: Scrii d * d < n cu < strict și pierzi cazul n = 4 (d=2, 2×2=4). Condiția corectă este d * d <= n.