prim013

#include <fstream>
#include <bitset>
#define N 10000001
using namespace std;
bitset <N> prim;

void Ciur()
{
    prim[0]=prim[1]=1; /// Ciurul lui Eratostene
    for(int i=2;i*i<N;++i)
        if(prim[i]==0)
            for(int j=2;i*j<N;++j)
                prim[i*j]=1;
}

int nrdivizori(int n)
{
    int nrdiv=1,j,exp=0;
    bool ok=false;
    while(n%2==0)
        n/=2,++exp;
    nrdiv*=(exp+1);
    for(j=3;j*j<=n&&n!=1&&!ok;j+=2)
    {
        exp=0;
        while(n%j==0)
        {
            n/=j;
            ++exp;
        }
        nrdiv*=(exp+1);
        if(n==1)
            ok=true;
    }
    if(n>1)
        nrdiv*=2;
    return nrdiv;
}

int main()
{
    ifstream f("prim013.in");
    Ciur();
    int n;
    f>>n;
    int x,nr=0;
    for(int i=0;i<n;++i)
    {
        f>>x;
        if(!prim[nrdivizori(x)])
            ++nr;
    }
    f.close();
    ofstream g("prim013.out");
    g<<nr;
    g.close();
    return 0;
}