11466 - Largest Prime Divisor

#include <iostream>
#include <cstdio>
#include <algorithm>
#include<cstring>
#include<cmath>
#include <vector>
#define N 10001000
using namespace std;

bool prime[N];
vector <long long> Primes;
vector <long long> Factors;
long long GenFacts(long long n);
void sieve ();
bool IsPrime (long long p);
int Neg;

int main ()
{
    long long n;
    freopen("in.txt","r",stdin);

    sieve();
    while(scanf("%lld",&n)&&n)
    {
        Neg=0;
        if(n<0)
            n *= -1,Neg=1;

        if(n<4||(n<N&&prime[n])||IsPrime(n))
        {
            printf ("-1\n");
            continue;
        }

        printf("%lld\n",GenFacts(n));
    }
    return 0;
}

long long GenFacts(long long n)
{
    int i,s=sqrt(n);
    long long tmp = n;
    Factors.clear();

    for(i=0;Primes[i]<=s;i++)
        while(tmp%Primes[i]==0)
        {
            tmp/=Primes[i];
            Factors.push_back(Primes[i]);
        }

    if(tmp>1)
        Factors.push_back(tmp);

    sort(Factors.begin(),Factors.end());

    if(Neg)return Factors[Factors.size()-1];
    if (Factors[0]==Factors[Factors.size()-1])
        return -1;
    return Factors[Factors.size()-1];
}

void sieve ()
{
    int i,j,s=sqrt(N);
    memset (prime,true,sizeof(prime));
    Primes.push_back(2);
    prime[0]=prime[1]=false;

    for(i=4;i<N;i+=2)
        prime[i]=false;

    for (i = 3;i<=s;i+=2)
        if (prime [i])
            for(j=i*i;j<N;j+=2 * i )
                prime[j]=false;

    for (i=3;i<N;i+=2)
        if (prime[i])
            Primes.push_back(i);
}

bool IsPrime (long long p)
{
    int s,i;
    if ( p < 2 || p % 2 == 0 ) return false;

    s = sqrt(p);

    for (i = 3; i<=s;i+=2 )
        if ( p % i == 0 )
            return false;
    return true;
}