|

Algoritmi Elementari – Testarea unui Număr Prim 11


1. Obiectivele lecției:

  • Să înțeleagă conceptul de număr prim.
  • Să învețe algoritmi pentru testarea dacă un număr este prim.
  • Să implementeze acești algoritmi în limbajul C++.
  • Să aplice algoritmi în probleme practice, cum ar fi generarea numerelor prime.

2. Conținutul lecției:

Ce este un număr prim?

  • Definiție: Un număr prim este un număr natural mai mare decât 1, care are exact doi divizori: 1 și el însuși.
  • Exemple: 2, 3, 5, 7, 11 sunt numere prime.
  • Contraexemple: 4, 6, 8, 9 nu sunt numere prime (au mai mult de doi divizori).

3. Algoritmul general:


Principiul de bază:

  1. Dacă numărul este mai mic decât 2, acesta nu este prim.
  2. Verifică dacă numărul este divizibil cu vreun alt număr, de la 2 până la √n.
  3. Dacă este divizibil, numărul nu este prim. Altfel, este prim.

Pseudocod pentru testarea unui număr prim:

Intrare: n

Dacă n < 2, atunci

    Nu este prim

Pentru i de la 2 la √n:

    Dacă n % i == 0, atunci

        Nu este prim

Este prim


4. Exemple practice:


Exemplu 1: Testarea unui singur număr

Cod în C++:

#include <iostream>

#include <cmath>

using namespace std;

int main() {

    int n;

    cout << „Introdu un numar: „;

    cin >> n;

    if (n < 2) {

        cout << n << ” nu este prim.” << endl;

        return 0;

    }

    bool estePrim = true;

    for (int i = 2; i <= sqrt(n); i++) {

        if (n % i == 0) {

            estePrim = false;

            break;

        }

    }

    if (estePrim) {

        cout << n << ” este prim.” << endl;

    } else {

        cout << n << ” nu este prim.” << endl;

    }

    return 0;

}


Exemplu 2: Afișarea numerelor prime până la un număr dat

Cod în C++:

#include <iostream>

#include <cmath>

using namespace std;

bool estePrim(int n) {

    if (n < 2) {

        return false;

    }

    for (int i = 2; i <= sqrt(n); i++) {

        if (n % i == 0) {

            return false;

        }

    }

    return true;

}

int main() {

    int limita;

    cout << „Introdu limita superioara: „;

    cin >> limita;

    cout << „Numerele prime pana la ” << limita << ” sunt: „;

    for (int i = 2; i <= limita; i++) {

        if (estePrim(i)) {

            cout << i << ” „;

        }

    }

    cout << endl;

    return 0;

}


Exemplu 3: Generarea primelor n numere prime

Cod în C++:

#include <iostream>

#include <cmath>

using namespace std;

bool estePrim(int n) {

    if (n < 2) {

        return false;

    }

    for (int i = 2; i <= sqrt(n); i++) {

        if (n % i == 0) {

            return false;

        }

    }

    return true;

}

int main() {

    int n, count = 0, numar = 2;

    cout << „Cate numere prime doresti? „;

    cin >> n;

    cout << „Primele ” << n << ” numere prime sunt: „;

    while (count < n) {

        if (estePrim(numar)) {

            cout << numar << ” „;

            count++;

        }

        numar++;

    }

    cout << endl;

    return 0;

}


5. Activități practice pentru elevi:

  1. Scrieți un program care determină dacă un număr este prim folosind doar bucla while.
  2. Realizați un program care determină suma tuturor numerelor prime mai mici decât un număr dat.
  3. Scrieți un program care afișează toate numerele prime dintre două valori introduse de utilizator.

6. Scheme logice:

  1. Testarea unui număr prim:
    • Start -> Verifică n < 2 -> (NU: trece la buclă) -> Verifică divizorii -> (DA: n % i == 0 -> Nu este prim) / (NU: Este prim) -> Stop.
  2. Afișarea numerelor prime până la o limită:
    • Start -> Pentru fiecare număr între 2 și limită -> Aplică testul de primalitate -> Afișează dacă este prim -> Stop.

7. Concluzie:

  • Testarea primalității este un algoritm fundamental în matematică și informatică.
  • Algoritmul de testare prin verificarea divizibilității până la √n este eficient pentru numere mari.
  • Prin implementarea acestor algoritmi, elevii vor înțelege mai bine conceptul de divizibilitate și optimizarea codului.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *