prim023_eficienta

#include <fstream>
using namespace std;
ifstream f("prim023.in");
ofstream g("prim023.out");
int n,i,j,NrCif,p,u,x,t,sol[32001],prim[3500];
bool EstePrim;

int main()
{
    sol[1]=1,sol[2]=0,NrCif=0;
    for(i=2;i<=32000;++i) /// prim[] va memora numerele prime pana la sqrt(1000000000) care-i aprox. 31623
        if(sol[i]==0)
        {
            prim[++NrCif]=i,j=i+i;
            while(j<=32000)
                sol[j]=1,j+=i; /// sol[j]=1 daca nu e numar prim si sol[j]=0 daca e numar prim
        }
    f>>n;
    u=0,p=0; /// u=nr de 1, iar p=nr de numere prime
    for(i=1;i<=n;++i) /// Citesc sirul de numere
    {
        f>>x;
        if(x==1) /// Daca e 1 il contorizez
            ++u;
        else /// altfel verific daca e prim si-l contorizez
        {
            EstePrim=true,j=1; /// presupunem ca x Este Prim
            while(prim[j]*prim[j]<=x&&EstePrim)
                if(x%prim[j]==0) /// Verificam daca x e prim (daca nu e, atunci lui EstePrim i se atribuie false
                {
					EstePrim=false;
					break;
				}
                else
                    ++j;
            if(EstePrim) /// Daca x e numar prim
                ++p;
        }
    }
    if(p==0)
        g<<0;
    else
        if(u==0)
            g<<p;
        else
        {
             sol[1]=p,NrCif=1; /// sol <- p
             for(i=1;i<=u;++i) /// Calculez p*2^u si pun rezultatul in sol[]
             {
                 t=0;
                 for(j=1;j<=NrCif;++j) /// sol <- sol*2
                     x=(sol[j]*2+t)%10,t=(sol[j]*2+t)/10,sol[j]=x;
                 while(t>0) /// Daca avem transport
                     sol[++NrCif]=t%10,t/=10;
             }
             for(i=NrCif;i>=1;--i) /// Afisez rezultatul
                g<<sol[i];
         }
    return 0;
}