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ă:
- Dacă numărul este mai mic decât 2, acesta nu este prim.
- Verifică dacă numărul este divizibil cu vreun alt număr, de la 2 până la √n.
- 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:
- Scrieți un program care determină dacă un număr este prim folosind doar bucla while.
- Realizați un program care determină suma tuturor numerelor prime mai mici decât un număr dat.
- Scrieți un program care afișează toate numerele prime dintre două valori introduse de utilizator.
6. Scheme logice:
- 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.
- 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.