Dându-se un număr natural n, să se determine dacă este sau nu prim.

Exemplu. Pentru n = 3, răspunsul va fi DA, pe când pentru n = 10, răspunsul va fi NU.

Ce este un număr prim?

Un număr prim este un număr natural care are exact doi divizori: 1 și el însuși.

Câteva curiozități

Numărul 1 nu este prim, deoarece are un singur divizor.

Cel mai mic număr prim este 2. Acesta este singurul număr par și prim.

Determinarea primalității unui număr (metoda naivă)

Un număr prim are exact doi divizori, iar toți divizorii unui număr n se găsesc între 1 și n. Așadar, o primă metodă de rezolvare ar fi să verificăm, pentru toate numerele de la 1 la n, dacă se găsește vreun număr care să fie divizor al lui n:

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int numarDivizori = 0;
    for(int d = 1; d <= n; d++) {
        if(n % d == 0) {
            numarDivizori++;
        }
    }
    if(numarDivizori == 2) {
        cout << "DA";
    } else {
        cout << "NU";
    }
    return 0;
}

Această problemă merge, dar nu este destul de eficientă. Pentru un număr mai mare, spre exemplu 1.000.000.000 (un miliard), s-ar efectua un miliard de operații, un număr imens.

Determinarea primalității unui număr (metoda optimizată 1)

Observăm următorul lucru: divizorii vin în perechi. Astfel, pentru un divizor d al lui n, cu d < sqrt(n), există un alt divizor, d' = n / d, cu proprietatea că d * d' = n și d' > sqrt(n). Prin urmare, putem să parcurgem divizorii doar până la radical, reducând semnificativ numărul de operații efectuate.

Observație. Majoritatea numerelor au un număr par de divizori (din acest motiv vin în perechi). Excepție fac numerele pătrate perfecte — acestea au divizor și pe sqrt(n), care este perechea sa (și care nu trebuie numărată de două ori! — evităm asta prin a verifica dacă n / d == d).

Pentru radical, putem folosi biblioteca <cmath> sau să mergem până când d * d ≤ n.

Implementare C++

Algoritmul este următorul:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int radical = sqrt(n), numarDivizori = 0;
    for(int d = 1; d <= radical; d++) {
        if(n % d == 0) { //Am găsit divizorul d, dar considerăm și perechea acestuia
            int dprim = n / d; //d' = n / d
            if(dprim != d) {
                numarDivizori += 2;
            } else { //Dacă d' == d, atunci perechea lui d este el însuși, deci îl numărăm doar o dată
                numarDivizori++;
            }
        }
    }
    if(numarDivizori == 2) {
        cout << "DA";
    } else {
        cout << "NU";
    }
    return 0;
}

Determinarea primalității unui număr (metoda optimizată 2)

O metodă și mai optimizată este următoarea:

• verificăm dacă n este par; dacă este și n ≠ 2, atunci nu mai are rost să verificăm divizorii acestuia, deoarece clar nu va fi prim; dacă n este chiar 2, atunci afișăm că este prim;
• luăm doar divizorii impari până la sqrt(n); n fiind impar, nu mai trebuie să verificăm dacă se împarte la numere pare.

Implementare C++

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    if(n == 2) { //Caz particular: n este 2
        cout << "DA";
    } else if(n < 2) { //Caz particular: n < 2 (nu va fi prim)
        cout << "NU";
    } else if(n % 2 == 0) { //n este > 2. Dacă este par, atunci nu poate fi prim
        cout << "NU";
    } else {
        int gasitDivizori = 0;
        for(int d = 3; d * d <= n; d += 2) { //Luăm divizori impari: 3, 5, 7, …
            if(n % d == 0) { //Am găsit un divizor diferit de 1 și de n, deci n nu este prim
                gasitDivizori = 1;
                break;
            }
        }
        if(gasitDivizori == 1) { //Dacă am găsit divizori diferiți de 1 și de n, atunci nu este prim
            cout << "NU";
        } else { //În sfârșit!!! n e prim 🤑
            cout << "DA";
        }
    }
    return 0;
}

Verifică instant dacă un număr este prim în C++

Mai ții minte Ciurul lui Eratostene? Este o lecție predată la matematică în clasa a șasea, prin care puteam să determinăm foarte ușor pentru primele n numere naturale, care sunt prime.

Ideea este următoarea: știm că 2 este prim, așadar toți multiplii lui 2 (4, 6, 8, …) nu sunt primi — îi marcăm într-un vector. Mergem la următorul număr nemarcat, 3. Asumăm astfel că este prim, așadar multiplii săi îi marcăm (6, 9, 12, …). Mergem la următorul număr nemarcat, 5. Repetăm procedeul și observăm faptul că numerele nemarcate sunt cele prime.

Pentru tot codul complet și explicații amănunțite, vă recomandăm acest articol de la 100din100.

Problemă propusă

Problema Este prim

Alte resurse și bibliografie

• Invata.info
• cwsin
• PbInfo
• 100din100