Spoj AMR10C - Square Free Factorization Solution

 

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

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;

#define ll long long int

const ll N=1e6;

vector<ll>prime;

ll i,j;

bool vis[N];

void sieve(int N)

{

    for(i=3; i*i<=N; i+=2)

    {

        if(vis[i]==0)

        {

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

            {

                vis[j]=1;

            }

        }

    }

    prime.push_back(2);

    for(i=3; i<=N; i+=2)

    {

        if(vis[i]==0)

        {

            prime.push_back(i);

        }

    }

}

int main()

{

    ll t,n,i,mx,cnt,cn,cp;

    sieve(100000);

    cin>>t;

    while(t--)

    {

        mx=1;

        cin>>n;

        cn=n;

        cnt=0;

        for(i=0; i<prime.size() && prime[i]*prime[i]<=cn; i++)

        {

            cnt=0;

            while(cn%prime[i]==0)

            {

                cnt++;

                cn/=prime[i];

            }

            mx=max(mx,cnt);

        }

        cout<<mx<<endl;

    }

}