daniela a fost fascinata la lectia de matemiatica de numerele prime. Ea a inceput sa aleaga numere din ce in ce mai mari ca sa le verifice daca sunt prime sau nu. Procesul de verificare este,insa,anevoios. Tu cum ai descrie un algoritm care verifica daca un numar este prin sau nu (Limbaj C++ va rog)

Răspuns:

#include <iostream>

using namespace std;

bool numarPrim(int numar) // Functia returneaza doar true sau false - pentru ca nu avem nevoie de alte valori

{

   if(numar < 2) // Daca numarul este mai mic ca si 2 (1, 0, -1, -2, etc) - acesta nu este prim

       return false;

   if(numar == 2) // Daca numarul este 2, acesta este prim

       return true;

   // for(int i = 2; i <= sqrt(numar); i++) - Optimizare in caz de nevoie

   for(int i = 2; i <= numar / 2; i++) // Parcurgem toate numerele de la 2 la numar / 2

       if(numar % i == 0) // Daca acesta se imparte exact la acel numar, inseamna ca nu este prim

           return false;

   return true;

}

int main()

{

   int nr;

   cin >> nr;

   if(numarPrim(nr) == true)

       cout << "Numarul este prim";

   else

       cout << "Numarul NU este prim";

   return 0;

}

Explicație: