Număr prim – algoritm eficient

Enunț

Se citeşte un număr natural n. Să se verifice dacă n este sau nu un număr prim.

Exemplu

Dacă n = 7, atunci algoritmul va afişa DA pentru că divizorii lui 7 sunt 1 și 7, deci 7 este număr prim.

Dacă n = 8, atunci algoritmul va afişa NU pentru că divizorii lui 8 sunt 1, 2, 4, 8,deci 8 nu este număr prim.

Descrierea metodei de rezolvare

Un algoritm mai eficient pentru determinarea dacă un număr este prim constă în verificarea divizorilor până la rădăcina pătrată a numărului n. Dacă n nu este divizibil cu niciun număr din intervalul [2, sqrt(n)], atunci n este prim.

Aceasta reduce considerabil numărul de verificări necesare.

Inițializare: Verificăm cazurile speciale pentru n mai mic sau egal cu 1, deoarece numerele 1 și mai mici nu sunt prime.
Verificarea divizorilor: Parcurgem toate numerele de la 2 până la rădăcina pătrată a lui n. Dacă n este divizibil cu oricare dintre aceste numere, atunci n nu este prim și ne putem opri.
Determinarea rezultatului: Dacă nu am găsit niciun divizor în intervalul [2, sqrt(n)], atunci n este prim.

Algoritmul în limbaj pseudocod

n întreg
estePrim bool
citeşte n
estePrim ← true
// Cazuri speciale
dacă n <= 1 atunci
|     estePrim ← false
|
|altfel
|    // Verificam divizorii de la 2 pana la sqrt(n)
|    pentru d ← 2, sqrt(n) execută
|    | dacă n % d = 0 atunci
|    | | estePrim ← false
|    | |▄
|    |▄
|▄
// Afișăm rezultatul
dacă estePrim = true atunci
| scrie "DA"
|altfel
| scrie "NU"
|▄

Algoritmul în limbaj de programare C/C++

/*****************************************************

numar prim - V2 eficient

******************************************************/
#include <iostream>
#include <cmath> // necesar pentru sqrt
using namespace std;

int main() {
    int n;
    bool estePrim = true;

    cout << "Introduceti un numar: ";
    cin >> n;

    // Cazuri speciale
    if (n <= 1) {
        estePrim = false;
    } else {
        // Verificam divizorii de la 2 pana la sqrt(n)
        for (int d = 2; d <= sqrt(n); d++) {
            if (n % d == 0) {
                estePrim = false;
                break; // Nu este nevoie sa continuam, stim ca n nu e prim
            }
        }
    }

    // Afișăm rezultatul
    if (estePrim) {
        cout << "DA" << endl;  // n este numar prim
    } else {
        cout << "NU" << endl;  // n nu este numar prim
    }

    return 0;
}