De ce contează?
Un număr prim e ca o cărămidă: nu-l poți „sparge" în bucăți întregi mai mici prin înmulțire. 7 nu se scrie ca produs de două numere mai mici decât el — doar 1×7. Numerele prime sunt cărămizile din care se construiesc toate celelalte numere.
Ce este un număr prim
Un număr n ≥ 2 este prim dacă are exact doi divizori: 1 și el însuși. Dacă mai are
și alți divizori, e compus.
- Prime: 2, 3, 5, 7, 11, 13, ...
- Compuse: 4 (=2·2), 6 (=2·3), 9 (=3·3), ...
1 nu este prim (are un singur divizor). 2 este prim — și e singurul prim par, fiindcă orice alt număr par se împarte la 2.
Algoritm pas cu pas: e prim 91?
Căutăm un divizor între 2 și √91 ≈ 9.5:
d | 91 % d | divide? |
|---|---|---|
| 2 | 1 | nu |
| 3 | 1 | nu |
| 4 | 3 | nu |
| 5 | 1 | nu |
| 6 | 1 | nu |
| 7 | 0 | da → 91 = 7 · 13 |
Am găsit un divizor (7), deci 91 nu e prim. Nici nu mai are rost să verificăm peste √91.
De ce ne oprim la √n
Dacă n are un divizor d mai mare decât √n, atunci perechea lui, n / d, e mai mică
decât √n — și am fi întâlnit-o deja. Deci e suficient să verificăm până la √n.
2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
Implementare C++
#include <iostream>
using namespace std;
bool estePrim(int n) {
if (n < 2) return false; // 0 si 1 nu sunt prime
for (int d = 2; (long long)d * d <= n; d++) {
if (n % d == 0) return false; // am gasit un divizor
}
return true; // niciun divizor -> prim
}
int main() {
cout << estePrim(91) << "\n"; // 0 (fals): 91 = 7 * 13
cout << estePrim(97) << "\n"; // 1 (adevarat): 97 e prim
return 0;
}return false de îndată ce găsești primul divizor — nu are rost să continui. Asta face
funcția rapidă pe numere compuse, care au adesea divizori mici.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| compus cu divizor mic | aproape O(1) | O(1) |
| prim sau divizor mare | O(√n) | O(1) |
Pentru a verifica multe numere mici (toate până la N), nu apela funcția de N ori — folosește Ciurul lui Eratostene (lecție separată), care e mult mai rapid pe interval.
Capcane reale la testul de primalitate:
- Uiți
n < 2: funcția spune că 0 și 1 sunt prime. Tratează-le explicit. - Bucla până la
n: O(n) per număr — prea lent dacă verifici multe valori. Mergi până la √n. - Overflow în
d * d: se sparge înintpentrunmare. Scrie(long long)d * d <= n. - Tratezi 2 greșit: unele soluții pornesc bucla de la 3 și uită că 2 e prim. Cu
d * d <= nși start de la 2, 2 iese corect (bucla nu intră,return true).
De reținut
- Prim = exact doi divizori (1 și el); 1 nu e prim, 2 e singurul prim par.
- Verifici divizori doar până la √n;
return falsela primul găsit. - Pentru toate primele până la N, folosește Ciurul, nu testul individual repetat.