Question

Scrie un program care determina daca un nr natural n este prim sau nu. +explicatie (ofer FUNDA)

Answer 1

Răspuns:

#include <iostream>

using namespace std;

bool este_prim(int numar)

{

   if(numar <= 1)

       return false;

   if(numar == 2)

       return true;

   if(numar % 2 == 0)

       return false;

   int divizor = 3;

   while(divizor * divizor <= numar)

   {

       if(numar % divizor == 0)

           return false;

       divizor += 2;

   }

   return true;

}

int main()

{

   int numar;

   cin >> numar

   if(este_prim(numar))

       cout << "Prim.";

   else

       cout << "Nu.";

   return 0;

}

Explicație:

O sa notez numarul cu "x" in explicatie

Matematic, daca x <= 1, x nu este prim. Daca x = 2, x este prim. Daca x este par (cu exceptia lui 2), x nu este prim. Tot matematic, stim ca daca un numar nu este prim, in intervalul $[2, \sqrt{x}]$ vom găsi cel puțin un divizor al acestuia. Astfel, putem elimina toate numerele care sunt $>\sqrt{x}$ sau care sunt pare. In acest fel restrangem cautarea la numerele impare din $[3, \sqrt{x}]$.