Numere prime și verificarea primalității

După ce am învățat despre divizori și multipli, următorul pas natural este să studiem numerele prime.

Numerele prime apar foarte des în:

• probleme de matematică;
• algoritmică de bază;
• criptografie;
• exerciții de concurs.

Ce este un număr prim?

Un număr natural n este prim dacă are exact doi divizori:

• 1
• n

Exemple:

• 2 este prim (divizori: 1, 2);
• 3 este prim (divizori: 1, 3);
• 5 este prim (divizori: 1, 5).

Ce este un număr neprim (compus)?

Un număr este compus dacă are mai mult de doi divizori.

Exemple:

• 4 are divizorii 1, 2, 4 -> compus;
• 6 are divizorii 1, 2, 3, 6 -> compus;
• 12 are mai mulți divizori -> compus.

Caz important: 0 și 1

• 0 nu este prim;
• 1 nu este prim.

Așadar, primul număr prim este 2.

Verificarea primalității - soluția simplă (ineficientă)

Ideea:

• numărăm câți divizori are n între 1 și n;
• dacă are exact 2, numărul este prim.

int n;
cin >> n;

int cnt = 0;
for (int d = 1; d <= n; d++) {
    if (n % d == 0) {
        cnt++;
    }
}

if (cnt == 2) {
    cout << "Prim";
} else {
    cout << "Neprim";
}

Input:
13

Output:
Prim

De ce este ineficientă?

Pentru fiecare număr verificăm toate valorile până la n, deci pentru numere mari este lentă.

Verificarea primalității - soluția eficientă

Observație:

Dacă n are un divizor diferit de 1 și n, atunci unul dintre divizori este cel mult sqrt(n).

Asta înseamnă că nu trebuie să verificăm până la n, ci doar până la:

d * d <= n

int n;
cin >> n;

if (n < 2) {
    cout << "Neprim";
} else {
    bool prim = true;

    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            prim = false;
            break;
        }
    }

    if (prim) {
        cout << "Prim";
    } else {
        cout << "Neprim";
    }
}

Input:
25

Output:
Neprim

Explicație pentru n = 25

• verificăm d = 2 -> nu divide;
• verificăm d = 3 -> nu divide;
• verificăm d = 4 -> nu divide;
• verificăm d = 5 -> divide (25 % 5 == 0);
• ne oprim -> 25 este neprim.

Afișarea numerelor prime până la n

Putem verifica fiecare număr de la 2 la n cu metoda eficientă.

int n;
cin >> n;

for (int x = 2; x <= n; x++) {
    bool prim = true;

    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0) {
            prim = false;
            break;
        }
    }

    if (prim) {
        cout << x << " ";
    }
}

Input:
20

Output:
2 3 5 7 11 13 17 19

Greșeli frecvente

1. Considerăm că 1 este prim

Greșit: 1 are un singur divizor, nu doi.

2. Pornim verificarea de la d = 1

Dacă începi de la 1, condiția n % 1 == 0 este mereu adevărată și nu ajută la testul de primalitate.

În varianta eficientă pornim de la d = 2.

3. Nu oprim bucla după ce găsim divizor

Dacă am găsit un divizor, știm deja că numărul este neprim.

break face programul mai rapid.

Ce să reții

• Un număr prim are exact doi divizori: 1 și el însuși.
• 0 și 1 nu sunt prime.
• Verificarea până la n este corectă, dar lentă.
• Verificarea până la sqrt(n) este mult mai eficientă.
• Pentru probleme practice, metoda cu d * d <= n este recomandată.

Probleme

pbinfoVerifprim→

pbinfoNprime→

pbinfoNumere10→

pbinfoDivizori3→