1.

/*
 * ACM Contest training
 * Problem: 11099 - Next Same-Factored
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=22&problem=2040
 *
 * @author Christoph Goettschkes
 * @version 1.0, 12/08/2010
 *
 * Method : Sieve of eratosthenes, prime factorization, dynamic programming
 * Status : Accepted
 * Runtime: 1.748
 */

import java.util.*;
import java.io.*;

class Main {

	static int[] primes;
	static int curNumber;
	static long curEnd;
	static long curResult;
	static Set<Integer> curSet;
	static HashMap<Integer, Long> answers = new HashMap<Integer, Long>();

	public static void main(String[] args) throws Exception {
		primes = sieve(1000000);
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder string = new StringBuilder();

		do
		{
			int n = Integer.parseInt(reader.readLine());
			long answer;
			if (n == 1)
				answer = 3000000;
			else
				answer = test(n);
			
			if (answer > 2000000)
				string.append("Not Exist!\n");
			else
				string.append(answer + "\n");
		} while(reader.ready());

		System.out.print(string);
	}

	static long test(int n) {
		if (answers.containsKey(n))
			return answers.get(n);

		curNumber = n;
		List<Integer> facs = factorize(curNumber);
		curSet = new HashSet<Integer>(facs);

		curEnd = curNumber * facs.get(0);
		curResult = Integer.MAX_VALUE;
		long start = 1;
		for (int i : curSet)
			start *= i;
		calc(start);
		answers.put(n, curResult);
		return curResult;
	}

	static void calc(long n) {
		if (n > curEnd || n > curResult)
			return;

		if (n < curResult && n > curNumber)
			curResult = n;

		for (int i : curSet) {
			calc(n * i);
		}
	}


	public static List<Integer> factorize(int n) {
		List<Integer> facs = new ArrayList<Integer>();

		int primeKey = 0;
		while (n > 1)
		{
			int curPrime = primes[primeKey];
			while (n % curPrime == 0) {
				facs.add(curPrime);
				n /= curPrime;
			}
			primeKey++;
		}

		return facs;
	}

	public static int[] sieve(int upperBound) {
		int upperBoundSquareRoot = (int)Math.sqrt(upperBound);
		List<Integer> primes = new ArrayList<Integer>();
		BitSet sieve = new BitSet(upperBound + 1);

		for (int m = 2; m <= upperBoundSquareRoot; m++)
			if (!sieve.get(m))
				for (int k = m*m; k <= upperBound; k += m)
					sieve.set(k, true);

		for (int m = 2; m <= upperBound; m++)
			if (!sieve.get(m))
				primes.add(m);

		
		int[] ret = new int[primes.size()];
		int key = 0;
		for (int i : primes)
			ret[key++] = i;
		
		return ret;
	}
}



2. 
/**
 * FWP:	Ausgewaehlte Probleme aus dem ACM (SS10)
 *
 * Method: Math: Primes
 * Problem: 11099 - NextSameFactored
 * Accepted: 2.588
 * @author Evgeni Pavlidis
 *
 */
import java.io.*;
import java.util.*;

class Main {

    // debugging 
    private static boolean DEBUG = false;
    private static Stack<Integer> stack = new Stack<Integer>();
    
    
    private static final int MAX = 1000000;
    private static final int LIMIT = 2000000;
    private static boolean[] isPrime = new boolean[MAX+1];
    // saves the prime factors for [x][...]
    private static int[][] factors = new int[MAX+1][7];
    // saves the number of prime factors for [x]
    private static int[] index = new int[MAX+1];

    // saves the minimum next number found so far  
    private static long min;
    

    private static void sievePrimes()
    {
        isPrime[2] = true;
        factors[2][index[2]++] = 2;
        for(int j = 4; j <= MAX; j+=2)
            factors[j][index[j]++] = 2;
           
        for(int i = 3; i <= MAX; i+=2)
            isPrime[i] = true;
        
        int root = (int)Math.sqrt(MAX);
        for(int i = 3; i <= root; i+=2)
            if(isPrime[i])
                for(int j = i+i; j <= MAX; j+=i)
                {
                    isPrime[j] = false;
                    factors[j][index[j]++] = i;
                }
    }
    
    private static void findNext(int n, long current)
    {
        if(current > min || current >= LIMIT)
            return;
        
        if(current > n)
            min = current;            
        
        // go through all prime factors    
        for(int i = 0; i < index[n]; i++)
        {
            current = current * factors[n][i];
            
            if(DEBUG)
            {
                stack.push(factors[n][i]);
                System.out.println(stack + " ==> " + current);
            }

            findNext(n, current);
            current = current / factors[n][i];
            
            if(DEBUG)
                stack.pop();
        }
    }
    
    private static long getNextPrime(int n)
    {              
        long base = 1;
        long next;
        
        // tests if n contains a prime that wasn't sieved
        int test = n;
        
        for(int i = 0; i < index[n]; i++)
        {
            while( test % factors[n][i] == 0 )
                test /= factors[n][i];
                
            base *= factors[n][i];
        }
        
        if(test != 1)
        {
            factors[n][index[n]++] = test;
            base *= test;
        }

        if(DEBUG)
        {
            System.out.println("Factors: " + Arrays.toString(factors[n]));
            stack.clear();
        }
        
        min = n*factors[n][0];
 
        findNext(n, base);
        
        return min;
    }    
        
    public static void main(String...args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String input;
        int n;
        long next;
        
        sievePrimes();
        
        while( (input = reader.readLine()) != null )
        {
             n = Integer.parseInt(input);
             
             // special case 
             if(n == 1)
             {
                System.out.println("Not Exist!");
                continue;
             }
             
             if(isPrime[n])
                next = (long)n*n;
             else
                next = getNextPrime(n);
            
            if(next > LIMIT)
                System.out.println("Not Exist!");
            else
                System.out.println(next);
        }
    }
}