Spoj DIV2 - Divisors 2 Solution

 

Problem Link: https://www.spoj.com/problems/DIV2/

Solution in C++:

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include <bits/stdc++.h>

using namespace std;

int const n = 1000000;

int divisors[n];

bool vis[n ];

vector<int>prime;

void sol()

{

    for(int i = 1; i <=n ; ++i)

    {

        for(int j = i; j <= n; j += i)

        {

            divisors[j]++;

        }

    }

    memset(vis,true,sizeof vis);

    for(int i = 1; i <=n ; ++i)

    {

        for(int j = i; j <= n; j += i)

        {

            if(divisors[j]<=3||j%i!=0||divisors[j]%divisors[i]!=0)

                vis[j]=false;

        }

    }

    for(int i=1; i<=n; i++)

    {

        if(vis[i])

            prime.push_back(i);

    }

}

int main()

{

   sol();

   for(int i=107;i<=prime.size();i+=108)

    cout<<prime[i]<<endl;

}