M2 L3 info Numere prime, variabilă logică

În limbajele de programare C/C++ deoarece nu au fost prevăzute de la început cu variabile logice de tipul „adevărat” sau „fals” putem folosi în acest scop o variabilă de tip întreg în care dacă avem valoarea 0(zero) spunem că are valoarea logică „fals” iar dacă avem orice valoare diferită de 0(zero) spunem că are valoarea logică „adevărat”.

Un număr prim este un număr întreg pozitiv care nu are divizori proprii. Programul de mai jos verifică dacă un număr întreg citit de la tastatură este prim.

#include <iostream>

int main() {
    using namespace std;

    int nr;
    cout << "Introduceti un numar intreg: ";
    cin >> nr;

    if (nr < 2) {
        cout << nr << " numarul trebuie sa fie mai mare sau egal cu 2" << endl;
    } else {
        int ePrim = 1; // 1 pentru prim, 0 pentru neprim
        int d = 2;
        while (d <= nr/2) {
            if (nr % d == 0) {
                ePrim = 0; // Gasit un divizor, deci nu e prim
                break;
            }
            ++d;
        }

        if (ePrim) {
            cout << nr << " este un numar prim." << endl;
        } else {
            cout << nr << " nu este un numar prim." << endl;
        }
    }

    return 0;
}

Explicație:

  1. Input: Programul solicită utilizatorului să introducă un număr întreg.
  2. Cazurile speciale:
    • Dacă numărul este mai mic decât 2, este direct declarat ca neprim (deoarece numerele prime sunt definite doar pentru valori mai mari sau egale cu 2).
  3. Verificarea primalității:
    • Folosește un int numit ePrim, inițializat cu valoarea 1 (considerăm numărul prim la început).
    • Bucla while verifică divizibilitatea numărului cu toți divizorii de la 2 până la rădăcina pătrată a numărului.
    • Dacă este găsit un divizor, ePrim devine 0 și bucla se oprește.
  4. Output: La final, în funcție de valoarea lui ePrim, se afișează dacă numărul este prim sau nu.

Hai să analizăm codul linie cu linie:

1. #include <iostream>

Această linie include biblioteca standard C++ care permite intrarea și ieșirea de date prin cin (pentru citire) și cout (pentru afișare).

2. int main()

Punctul de intrare al programului. Toate instrucțiunile care urmează vor fi executate de la această funcție.

3. using namespace std;

Această linie permite utilizarea elementelor din namespace-ul std fără a scrie explicit prefixul std::. De exemplu, putem scrie cin și cout în loc de std::cin și std::cout.

4. int nr;

Declară o variabilă de tip întreg, numită nr, care va stoca numărul introdus de utilizator.

5. cout << "Introduceti un numar intreg: ";

Afișează mesajul pe ecran, cerând utilizatorului să introducă un număr întreg.

6. cin >> nr;

Citește un număr întreg de la tastatură și îl stochează în variabila nr.

7. if (nr < 2) {

Această condiție verifică dacă numărul introdus este mai mic decât 2. Numerele mai mici de 2 (cum ar fi 1, 0, sau numere negative) nu sunt prime, deci programul va afișa un mesaj corespunzător.

8. cout << nr << " numarul trebuie sa fie mai mare sau egal cu 2" << endl;

Dacă numărul este mai mic decât 2, acest mesaj este afișat, iar programul se termină pentru acel caz.

9. } else {

Dacă numărul este mai mare sau egal cu 2, se trece la blocul else, unde programul verifică dacă numărul este prim.

10. int ePrim = 1;

Aceasta este o variabilă de tip întreg folosită pentru a determina dacă numărul este prim:

  • Valoarea 1 înseamnă că numărul este considerat prim până la proba contrarie.
  • Valoarea 0 indică faptul că numărul nu este prim (are divizori).

11. int d = 2;

Aceasta este o variabilă care reprezintă un potențial divizor al numărului. Inițial, începe de la 2, cel mai mic divizor posibil al unui număr mai mare decât 1.

12. while (d <= nr / 2) {

Bucla while verifică dacă există vreun divizor între 2 și nr / 2 (inclusiv). Numerele mai mari decât nr / 2 nu trebuie verificate, deoarece, dacă există un divizor, acesta este mai mic sau egal cu jumătatea numărului.

13. if (nr % d == 0) {

Această condiție verifică dacă nr este divizibil cu d:

  • Dacă restul împărțirii (nr % d) este 0, înseamnă că d este un divizor al lui nr.

14. ePrim = 0;

Dacă s-a găsit un divizor, se setează variabila ePrim la 0, indicând că numărul nu este prim.

15. break;

Iese imediat din bucla while, deoarece numărul nu mai trebuie verificat în continuare – știm deja că nu este prim.

16. ++d;

Incrementarea variabilei d pentru a verifica următorul posibil divizor.

17. if (ePrim) {

După ce bucla se termină, se verifică valoarea lui ePrim. Dacă este încă 1, înseamnă că numărul nu a avut divizori și este prim.

18. cout << nr << " este un numar prim." << endl;

Dacă ePrim este 1, afișează că numărul este prim.

19. } else {

Dacă ePrim este 0, înseamnă că numărul nu este prim.

20. cout << nr << " nu este un numar prim." << endl;

Afișează că numărul nu este prim.

21. return 0;

Finalul funcției main. Programul returnează 0, indicând că s-a terminat cu succes.

Exemplu de rulare

Intrare:

Introduceți un număr întreg: 7

Ieșire:

7 este un număr prim.

Intrare:

Introduceți un număr întreg: 4

Ieșire:

4 nu este un număr prim.

Temă

Să se modifice programul de mai sus astfel încât să afișeze toate numerele prime mai mici decât un număr întreg n citit de la tastatură.

Rezolvarea temei: 

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "Introduceti un numar intreg: ";
    cin >> n;

    if (n < 2) {
        cout << "Nu exista numere prime mai mici decat " << n << "." << endl;
    } else {
        int numar = 2; // Începem de la primul număr prim
        while (numar <= n) {
            int ePrim = 1; // Presupunem că numărul este prim
            int d = 2; // Divizorul începe de la 2

            // Verificăm dacă numărul este prim
            while (d <= numar / 2) {
                if (numar % d == 0) {
                    ePrim = 0; // Dacă există un divizor, nu este prim
                    break;
                }
                ++d;
            }

            // Dacă numărul este prim, îl afișăm
            if (ePrim) {
                cout << numar << " ";
            }

            ++numar; // Trecem la următorul număr
        }
        cout << endl; // Linie nouă la final
    }

    return 0;
}