11466 - Largest Prime Divisor

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2461

Solution Idea : Prime factorization. n can be negative.

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool status[10000055];

vector<ll int>prime;

ll int cnt=0;

void sieve()
{
    ll int n=10000000;
    ll int sq=sqrt(n);

    prime.push_back(2);

    for(int i=4; i<=n; i=i+2) status[i]=1;

    for(int i=3; i<=sq; i=i+2)
    {
        if(status[i]==0)
        {
            for(int j=i*i; j<=n; j=j+i)
            {
                status[j]=1;
            }
        }
    }
    status[1]=1;
    status[0]=1;

    for(int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

ll int nod(ll int n)
{

    ll int sq=sqrt(n);
    ll int mx=1;
    cnt=0;

    for(int i=0; i<prime.size() && prime[i]<=sq; i++)
    {

        if(n%prime[i]==0)
        {
            cnt++;
            while(n%prime[i]==0)
            {
                n=n/prime[i];

            }
            sq=sqrt(n);

            mx=max(mx,prime[i]);

        }
    }
    if(n!=1)
    {
        cnt++;
        mx=max(mx,n);

    }
    return mx;
}

int main()
{

    ll int n,s;
    sieve();

    while(scanf("%lld",&n) and n)
    {
        if(n<0) n=-1*n;
        s=nod(n);

        if( cnt<=1) printf("-1\n");

        else printf("%lld\n",s);
    }
}