Question

Stie cineva de ce imi da limita de timp depasita la problema 404 de pe pbinfo?
Cerinţa
Se dă un șir cu n numere naturale. Determinați numărul total de cifre al tuturor numerelor prime din șir.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale.

Date de ieşire
Programul afișează pe ecran numărul C, reprezentând numărul total de cifre al tuturor numerelor prime din șir.

Restricţii şi precizări
1 ≤ n ≤ 1000
cele n numere citite vor fi mai mici decât 1.000.000.000
Exemplu:
Intrare

6
83 36 53 401 90 7
Ieșire

8
Explicație
Dintre cele 6 numere citite sunt prime : 83 53 401 7. În total, ele au 8 cifre.

Answer 1

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

Answer 2

#include <bits/stdc++.h>

using namespace std;

int main()

{

   int n , x , cnt = 0 , S = 0;

   cin >> n;

   for(int i = 1; i <= n ; ++i)

   {

       cin >> x;

       bool prim = true;

       if(x < 2)

           prim = false;

       for(int d = 2 ; d * d <= x && prim ; ++d)

       {

           if(x % d == 0)

               prim = false;

       }

       if(prim)

       {

           while(x)

           {

               cnt++;

               x = x / 10;

           }

       }

       S = S + cnt;

       cnt = 0;

   }

   cout << S;

   return 0;

}