Simplu. Algoritmul tau este ineficient! Probabil ca faci un for de la 1 la numarul dorit, numarandu-i divizorii. Apoi, daca are 2 divizori (1 si el insusi), este prim. Metoda asta este corecta, dar extrem de ineficienta. De ce?
Presupunem ca n = 1000 si toate cele n numere au peste 8 cifre. Asta inseamna ca vei face peste 1miliard ×1000 × 9 calcule (mai intai toti divizorii, apoi toate cifrele, de n ori)
Solutia? Imi vin 3 solutii eficiente in minte acum. Una din ele necesita functie, una vectori, iar cealalta e mai greut de inteles. Ti le voi enumera pe toate, poti cauta pe net pt mai multe detalii
1. Ciurul lui Eratostene (vectori): cu un ciur se cerne malai, deci poti gandi ca algoritmul "cerne" numerele ce nu sunt prime, si ramai cu cele prime. (destul de eficient, iti genereaza primele 1milion de numere prime repejor, dar poti ramane fara memorie mai departe)
2. Functie eficienta:
Codul:
#include <iostream>
using namespace std;
bool estePrim(int x)
{
if(x==1) return 0;
if(x%2==0 && x!=2 ) return 0;
for(int d=3; d*d<=x; d+=2)
if(x%d==0) return 0;
return 1;
}
int main()
{
int n;
int i,nrc,nr_total=0;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>x;
nrc=0;
if(estePrim(x))
{
//calculezi aicea nr de cifre, nu mai scriu eu
}
}
cout<<nr_total;
return 0;
}
3. Divizorii pana la parte intreaga din radical
In loc sa mergi cu for pana la x, mergi pana la partea intreaga din x. Codul este atasat
