1.

/*
* ACM Contest training
* Problem: 10392 Factoring Large Numbers
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=15&problem=1333
*
* @author Christoph Göttschkes
* @version 1.0, 10/19/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.276
*/

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

class Main
{

public static void main(String[] args) throws Exception {
find_primes(1000000);

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
long number = Long.parseLong(reader.readLine());

while (number >= 0) {
if (number == 1)
System.out.println(" " + 1);
else if (number == 0)
System.out.println(" " + 0);
else {
List<Long> facs = factors(number);

for (long n: facs)
System.out.println(" " + n);
}
number = Long.parseLong(reader.readLine());

System.out.println();
}

}

public static List<Long> factors(long number) {
List<Long> facs = new ArrayList<Long>();

for (int p: primes) {
if (p == 0)
continue;
while (number % p == 0) {
facs.add(new Long(p));
number /= p;
}
if (p > number)
break;
}

if (number > 1)
facs.add(number);

return facs;
}

public static int[] primes;

public static void find_primes(int max)
{
int i, j, k, divisor, offset;

double sqrt = Math.sqrt(max)+1;
int tmp[];

if(max > 100) {
primes = new int[max/2];
} else {
primes = new int[max];
}
primes[0] = 2;
primes[1] = 3;

for(i = 2, j = 5; j < max ; j += 2) {
if(j % 3 != 0) {
primes[i++] = j;
}
}

for(i = 2, divisor = 5, offset = primes.length; divisor < sqrt ; )
{
j = i * i;
tmp = new int[offset];
offset = j;

/*
* Copy the numbers that have already been sieved to a new array.
*/
System.arraycopy(primes, 0, tmp, 0, j);
while( j < tmp.length)
{
k = primes[j++];
if(k == 0)
{
/*
* The array may contain some zeros at the end. It's too much
* trouble to calculate the exact size for the array. Easier
* to pad with zeros
*/
break;
}
if(k % divisor != 0)
{
tmp[offset++] = k;
}
}
primes = null;
primes = tmp;
tmp = null;
divisor = primes[i++];
}
}

}



2.

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

class Main {


public static final int MAX = 1000000;
public static final boolean[] isPrime = new boolean[MAX+1];
public static final int prime[] = new int[MAX];
public static int maxPrime = 0;
private static int a,b,c,d;

private static void sievePrimes()
{
for(int i = 2; i <= MAX; i++)
isPrime[i] = true;
// sieve the multiples of 2
for(int i = 4; i <= MAX; i+=2)
isPrime[i] = false;

prime[maxPrime++] = 2;

// sieve other numbers
int squareRoot = (int)Math.sqrt(MAX);
for(int i = 3; i <= MAX; i+=2)
if(isPrime[i])
{
prime[maxPrime++] = i;
for(int j = i+i; j <= MAX; j += i)
isPrime[j] = false;
}

/** /
for(int i = 1; i < maxPrime; i++)
System.out.println(prime[i]);
/**/

}

private static void calc(long n)
{
for(int i=0; i < maxPrime; i++)
{
while(n % prime[i] == 0)
{
n /= prime[i];
System.out.println(" " + prime[i]);

}
}

if(n != 1)
System.out.println(" " + n);

}

public static void main(String...args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String input;
long n;

sievePrimes();

while((input = reader.readLine()) != null)
{
n = Long.parseLong(input);
if(n < 0)
break;

calc(n);
System.out.println();
}
}
}