Question

Să se scrie o funcție C++ care verifică dacă un număr natural transmis ca parametru este prim.

Restricţii şi precizări
numele funcției scrise este prim
funcția are un parametru, număr natural; valoarea sa va fi mai mică decât 1000000000
rezultatul funcției este 1 dacă valoarea parametrului este număr prim, respectiv 0 în caz contrar
Important
Soluția propusă va conține doar funcția cerută. Introducerea în soluție a altor instrucțiuni poate duce la erori de compilare sau de execuție, care vor duce la depunctarea soluției.

AM DOAR 90 DE PUNCTE
#include

using namespace std;
int prim(int x){
int i,nr=0;
for(i=1;i<=x;i++){
if(x%i==0)
nr++;}
if(nr==2)
return 1;
else
return 0;
}

Answer 1

Daca iti da doar 90 de puncte inseamna ca algoritmul e bun insa nu destul de rapid (ultimele ~10 teste cuprind numere foarte mari iar algoritmul tau nu pare prea eficient). Poti face cateva optimizari:
   Un numar prim se imparte doar la 1 si la el insusi. Daca se imparte la mai multe numere nu este prim. Deci ai o conditie de iesire din acel loop (cand nr e mai mare de 2.)
    Astfel codul va deveni:

using namespace std;
int prim(int x){
int i,nr=0;
for(i=1;i<=x;i++){
    if(x%i==0)
       nr++;
    if(nr>2) break;  //nu mai trebuie sa cauti si alti divizori
}
if(nr==2)
return 1;
else
return 0;
}

O alta optimizare ar fi:
   Niciun numar par nu este prim. Deci daca nr e diferit de doi inseamna automat ca nu e prim. Insa daca nu e par inseamna ca-l poti impartii doar la 3,5,7,9,11 (adica doar numere impare) pentru a vedea daca e prim sau nu.
   De asemena poti cauta divizori doar pana la radical din nr(dupa radical divizorii se repeta:Ex:36 (rad=6) Un divizor e 2 insa cand il imparti pe 36 la 18 iti da tot 2).
   Algoritmul complet (optimizat) il postez aici(il poti studia):

bool Prim(int nr){
   int rad=sqrt(nr);
   if(nr<2) return false;
   if(nr==2||nr==3){
     return true;
  }else{
      if(nr%2==0) return false;
      for(int i=3;nr<=rad;i+=2)
         if(nr%i==0) return false;
   
          return true;
  }
}
E complet optimizat.

Answer 2

#include <cmath>
int prim(int n)
{
    long long i;
    if(n==0 || n==1)
        return 0;
    for(i=2;i<=sqrt(n);i++)
        if(n%i==0)
            return 0;
    return 1;
}