Kattis Non-Prime Factors Solution

#include<bits/stdc++.h>

#define ll long long int

#define N 2000000

using namespace std;

int p[N+1];

int a[N+1];

void seive()

{

    ll i, j;

    ll l = sqrt(N);

    p[0] = p[1] = 1;

    for(i=2;i<=l;i++)

    {

        if(p[i] == 0)

        {

            for(j=i*i;j<=N;j+=i)

                p[j] = 1;

        }

    }

    for(i=1;i<=N;i++)

    {

        if(p[i] == 0)

            continue;

        for(j=i;j<=N;j+=i)

            a[j]++;

    }

}

int main()

{

    seive();

    ll n, m, i;

    scanf("%lld", &m);

    for(i=1;i<=m;i++)

    {

        scanf("%lld", &n);

        ll x = a[n];

        printf("%lld\n", x);

    }

    return 0;

}