UVa: 11466 (Largest Prime Divisor)



// http://uva.onlinejudge.org/external/114/11466.html
// Runtime: 0.360s
// Tag: prime, sieve, long long


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 10001000
#define LL long long
using namespace std;

bool mark [N];
vector <LL> primeList;
vector <LL> primeFactors;
bool isNegative;

bool isPrime (LL p)
{
    if ( p < 2 || p % 2 == 0 ) return false;

    int len = sqrt (p * 1.0);

    for ( int i = 3; i <= len; i += 2 ) {
        if ( p % i == 0 ) return false;
    }

    return true;
}

void sieve ()
{
    memset (mark, true, sizeof (mark));

    mark [0] = mark [1] = false;

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

    for ( int i = 3; i * i <= N; i += 2 ) {
        if ( mark [i] ) {
            for ( int j = i * i; j < N; j += 2 * i ) mark [j] = false;
        }
    }

    primeList.clear ();
    primeList.push_back (2);

    for ( int i = 3; i < N; i += 2 ) {
        if ( mark [i] ) primeList.push_back (i);
    }

    //printf ("%d\n", primeList.size ());
}

LL findPrimeFactors (LL n)
{
    int ind = 0;
    LL tmp = n;
    primeFactors.clear ();

    while ( primeList [ind] * primeList [ind] <= n ) {
        while ( tmp % primeList [ind] == 0 ) {
            tmp /= primeList [ind];
            primeFactors.push_back (primeList [ind]);
        }
        ind++;
    }

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

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

    if ( isNegative ) return primeFactors [primeFactors.size() - 1];

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

int main ()
{
    sieve ();

    LL n;

    while ( cin >> n && n ) {
        if ( n < 0 ) { n *= -1; isNegative = true; }

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

        cout << findPrimeFactors (n) << endl;

        isNegative = false;

    }
	return 0;
}

// @END_OF_SOURCE_CODE

3 thoughts on “UVa: 11466 (Largest Prime Divisor)

  1. Input:
    32
    -32
    -1
    1
    2
    3
    25412689632451
    23554125478568
    -96325415789658
    32145222225856
    32547854125223
    99999999999999
    11111111111111
    99999999999998
    99999999999997
    -16
    -17
    -19
    -24
    0
    Output:
    -1
    2
    -1
    -1
    -1
    -1
    1164409
    363444721
    3912804281
    3525017
    21441599
    909091
    909091
    7142857142857
    119189511323
    2
    -1
    -1
    3
    
  2. hi
    because, prime factor of 32 is = 2 * 2 * 2 * 2 * 2
    right?
    for input 32, output should be -1 … reason is, we have only one distinct prime divisor 2

    prime factor of -32 is = 2 * 2 * 2 * 2 * -2
    here we have two distinct prime number, 2 and -2
    largest prime factor of -32 is 2

    the trick is, we should consider the negative numbers as well for defining prime and prime divisor

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s