👤
a fost răspuns

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;
}

Răspuns :

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.
IONUTG38ZE
#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;
}
Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Ne dorim ca informațiile furnizate să vă fi fost utile. Dacă aveți întrebări sau aveți nevoie de suport suplimentar, nu ezitați să ne contactați. Revenirea dumneavoastră ne bucură, iar pentru acces rapid, adăugați-ne la favorite!


Ze Lesson: Alte intrebari