prim023

#include <cstdio>
#include <cmath>
#define BAZA 100000
using namespace std;
typedef int Huge[1000];
FILE *g=fopen("prim023.out","w+");

bool prim(int n)
{
    if(n==2||n==3)
        return true;
    else
        if(n==1||n==0)
            return false;
    if(n%2==0||n%3==0)
        return false;
    for(int k=1;6*k-1<=sqrt(n);++k)
        if(n%(6*k-1)==0||n%(6*k+1)==0)
            return false;
    return true;
}

void DoiLaN(Huge A,int n) /// A <- 2^n
{
    A[0]=1,A[1]=1; /// A <- 1 (adica 2^0)
    if(n==0)
        return;
    int p=0,T,C;
    do
    {
        T=0; /// T retine cifra de transport
        for(int i=1;i<=A[0];++i)
        {
            C=(A[i]<<1)+T; /// C <- A[i]*2 (Calculam cifra curenta C din A[i])
            T=C/BAZA; /// Calculam transportul
            A[i]=C%BAZA; /// si cifra curenta din A[i]
        }
        if(T!=0) /// Daca exista cifra de transport, in A ne trebuie inca un element
            A[++A[0]]=T; /// si in acest element punem cifra de transport
        ++p; /// Am efectuat o inmultire cu 2, puterea p creste
    } while(p!=n); /// pana cand puterea p este egala cu exponentul n
}

void Mult(Huge H,int X) /// H <- H*X
{ int i;
  unsigned long long T=0;
  for (i=1;i<=H[0];i++)
    { H[i]=H[i]*X+T;
      T=H[i]/BAZA;
      H[i]=H[i]%BAZA;
    }
  while (T) /// Cat timp exista transport
    { H[++H[0]]=T%BAZA;
      T/=BAZA;
    }
}

void Afisez(Huge X)
{
    fprintf(g,"%d",X[X[0]]);
    for(int i=X[0]-1;i>0;--i)
        fprintf(g,"%05d",X[i]);
    fprintf(g,"\n");
}

int main()
{
    int n,x,p=0,u=0;
    FILE *f=fopen("prim023.in","r");
    fscanf(f,"%d ",&n);
    for(int i=1;i<=n;++i)
    {
        fscanf(f,"%d ",&x);
        if(x==1)
            ++u;
        else
            if(prim(x))
                ++p;
    }
    fclose(f);
    if(u==0||u==n||p==0||p==n)
    {
        fprintf(g,"%d\n",p);
        return 0;
    }
    Huge sol;
    DoiLaN(sol,u);
    Mult(sol,p);
    Afisez(sol);
    fclose(g);
    return 0;
}