1.

/*
* ACM Contest training
* Problem: 583 - Prime Factors
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=524
*
* @author Christoph Goettschkes
* @version 1.0, 11/08/2010
*
* Method : Sieve of Eratosthenes
* Status : Accepted
* Runtime: 1.860
*/

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

class Main
{
static List<Integer> primes = new LinkedList<Integer>();


public static void main(String[] args) throws Exception {
sieve((int)Math.sqrt(2147483647));

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

int cur = Integer.parseInt(reader.readLine());

while (cur != 0) {
StringBuilder sb = new StringBuilder();
sb.append(cur);
sb.append(" = ");

boolean minus = cur < 0;
if (minus) {
cur *= -1;
sb.append("-1 x ");
}
for (int p : factor(cur)) {
sb.append(p + " x ");
}
System.out.println(sb.substring(0, sb.length()-3));

cur = Integer.parseInt(reader.readLine());
}
}

public static List<Integer> factor(int n)
{
List<Integer> facs = new LinkedList<Integer>();

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

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

return facs;
}

public static void sieve(int upperBound) {
long last = 0;

long upperBoundSquareRoot = (int) Math.sqrt(upperBound);
BitSet isComposite = new BitSet(upperBound);

for (long m = 2; m <= upperBoundSquareRoot; m++) {
if (!isComposite.get((int)m)) {
primes.add((int)m);
last = m;
for (long k = m * m; k <= upperBound; k += m) {
isComposite.set((int)k, true);
}
}
}

if (upperBoundSquareRoot == last)
upperBoundSquareRoot++;

for (int m = (int)upperBoundSquareRoot; m <= upperBound; m++) {
if (!isComposite.get(m)) {
primes.add(m);
}
}
}
}

2.

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

class Main {


public static final int MAX = (int)Math.sqrt(2147483648l);
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 String calc(int n)
{
StringBuffer result = new StringBuffer();

if(n < 0)
{
result.append(" x -1");
n = n * -1;
}

for(int i=0; i < maxPrime; i++)
while(n % prime[i] == 0)
{
n /= prime[i];
result.append(" x " + prime[i]);
}

if(n != 1)
result.append(" x " + n);

result.delete(0, 3);

return result.toString();
}

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

sievePrimes();

while( (input = reader.readLine()) != null )
{
n = Integer.parseInt(input);
if(n == 0)
break;

System.out.println(n + " = " + calc(n));
}
}
}