CubPrim

#include <bits/stdc++.h>
#define ULL unsigned long long int
#define MAX 2642245
#define Check(n) (status[n/64] & (1 << ((n % 64) / 2)))
#define Set(n) (status[n/64] |= (1 << ((n % 64) / 2)))
using namespace std;
ifstream fin("cubprim.in");
ofstream fout("cubprim.out");

int status[MAX/64 + 2];
ULL cuburi[200001], nr;
int n, lc, lcb=1, pz;
void seive()
{
    int limit = sqrt(MAX);
    for(int i = 3; i <= limit; i += 2)
    {
        if(!Check(i))
        {
            for(int j = i * i; j <= MAX; j += i + i)
                Set(j);
        }
    }
    cuburi[1]=8;
    for(size_t i = 3; i <= MAX; i += 2)
        if(!Check(i))
            cuburi[++lcb]=1ULL*i*i*i;
}
struct cubprim
{
    ULL val;
    int cb, poz;
};

cubprim v[200002];
int CompareCubprime(cubprim a, cubprim b)
{
    if(a.val != b.val)
        return a.val > b.val;
    return a.poz<b.poz;
}
int binarySearch(ULL arr[], int l, int r, ULL x)
{
    while (l <= r)
    {
        int mi = l + (r - l) / 2;
        if (arr[mi] == x)
            return mi;
        if (arr[mi] < x)
            l = mi + 1;
        else
            r = mi - 1;
    }
    return -1;
}

int main()
{
    seive();
    fin>>n;
    for(int i=1; i<=n; ++i)
    {
        fin>>nr;
        if(nr>7)
        {
            pz=binarySearch(cuburi,1,lcb,nr);
            if(pz>0)
            {
                long double cub_root=round(pow(nr, 1.0/3.0));
                if(cub_root*cub_root*cub_root==nr)
                {
                    ++lc;
                    v[lc].poz=i;
                    v[lc].val=nr;
                    v[lc].cb=(int)cub_root;
                }
            }
        }
    }
    sort(v+1, v + lc +1, CompareCubprime);
    fout<<lc<<'\n';
    for(int i=1; i<=lc; ++i)
        fout<<v[i].poz<<" "<<v[i].cb<<" "<<v[i].val<<'\n';
    return 0;
}