spoj solution: DIV - Divisors

#include <bits/stdc++.h>
#define pb push_back
#define Max 1000009
#define lim 1000006
using namespace std;
typedef  long long ll;
vector<int>prime;
bool mark[Max];
void sieve()
{
    for(int i=3; i<=sqrt(Max); i+=2)
    {
        if(!mark[i]) for(int j=i*i; j<Max; j+=i) mark[j]=true;
    }
    prime.pb(2);
    for(int i=3; i<=Max; i+=2) if(!mark[i]) prime.pb(i);
}

int ary[1000006];
bool chk[Max];
int main()
{


    sieve();
    for(int i=1; i<=1000001; i++)
    {
        for(int j=i; j<=1000001; j+=i) ary[j]++;
    }
    //  printf("%d",ary[100]);
    map<int,int>mp;
    int c=0;
    for(int i=1; i<=1000001; i++)
    {
        int d=ary[i];
        if(!chk[d])
        {
            int  sum=1;
            mp.clear();
            for(int j=0; prime[j]*prime[j]<=d; j++)
            {
                if(d%prime[j]==0)
                {
                    sum*=prime[j];
                    mp[prime[j]]++;
                    while(d%prime[j]==0) d/=prime[j];
                }
            }
            if(d!=1) sum*=d;
            if(d!=1) mp[d]++;
            if(mp.size()==2&&sum==ary[i])
            {
                c++;
                chk[ary[i]]=true;
                if(c%9==0)  printf("%d\n",i);

            }
        }
        else
        {
            c++;
            //chk[ary[i]]=true;
            if(c%9==0)  printf("%d\n",i);

        }
    }



    return 0;
}