PrimeQuery_TESTER

#include <bits/stdc++.h>
#include <algorithm>
#define Nmax 15001
#define ull unsigned long long

using namespace std;

ifstream fin("primequery.in");
ofstream fout("primequery.out");

unsigned long long V[Nmax] , C[Nmax] ;
int D[Nmax];

ull power(ull x, ull y, ull p)
{
    ull res = 1;
    x = x % p;

    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;

        y = y / 2;
        x = (x * x) % p;
    }
    return res;
}

bool miillerTest(ull d, ull n)
{
    ull a = 2 + rand() % (n - 4);

    ull x = power(a, d, n);

    if (x == 1  || x == n-1)
       return true;

    while (d != n-1)
    {
        x = (x * x) % n;
        d *= 2;

        if (x == 1)      return false;
        if (x == n-1)    return true;
    }

    return false;
}

bool isPrime(ull n, ull k)
{
    if (n <= 1 || n == 4)  return false;
    if (n <= 3) return true;
    if(n == 5) return true;

    ull d = n - 1;
    while (d % 2 == 0)
        d /= 2;

    for (ull i = 0; i < k; i++)
         if (!miillerTest(d, n))
              return false;

    return true;
}
int main()
{
    int n , k = 0;

    fin >> n;

    for(int i = 1 ; i <= n ; i++)
    {
        fin >> V[i];

        if(isPrime(V[i] , 600))
            C[++k] = V[i];

            D[i] = k;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        int c = 0;

        for(int j = 1 ; j <= D[i] ; j++)
        {
            if(C[j] < V[i])
                c++;
        }

        fout << c << " ";
    }
}