import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; /** * Created by dhruv.pancholi on 05/11/16. */ public class Main { public static List<Integer> getPrimeFactors(int N, List<Integer> primes) { List<Integer> factors = new ArrayList<Integer>(); int index = 0; int factor = primes.get(index); int limit = (int) Math.sqrt(N) + 1; while (N != 1 && factor < limit) { while (N % factor == 0) { N /= factor; factors.add(factor); } factor = primes.get(++index); } if (N != 1) factors.add(N); return factors; } public static void main(String[] args) throws FileNotFoundException { InputReader in = new InputReader(System.in); SieveOfEratosthenes soe = new SieveOfEratosthenes((int) Math.sqrt(Integer.MAX_VALUE) * 10); List<Integer> primes = soe.getPrimes(); int n; while (true) { n = in.nextInt(); if (n == 0) break; List<Integer> factors = getPrimeFactors(Math.abs(n), primes); System.out.print(n + " = "); if (n < 0) System.out.print("-1 x "); for (int i = 0; i < factors.size() - 1; i++) { System.out.print(factors.get(i) + " x "); } System.out.println(factors.get(factors.size() - 1)); } } private static class SieveOfEratosthenes { private boolean[] a; public SieveOfEratosthenes(int N) { a = new boolean[N + 1]; for (int i = 0; i <= N; i++) { a[i] = true; } a[0] = false; a[1] = false; int root = (int) Math.sqrt(N); for (int i = 2; i <= root; i++) { for (int j = 2 * i; j <= N; j += i) { a[j] = false; } } } public boolean[] getArray() { return a; } public boolean isPrime(int n) { return a[n]; } public List<Integer> getPrimes() { List<Integer> list = new ArrayList<Integer>(); for (int i = 1; i < a.length; i++) { if (a[i]) { list.add(i); } } return list; } } public static class InputReader { private BufferedReader reader; private StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public long nextLong() { return Long.parseLong(next()); } public int nextInt() { return Integer.parseInt(next()); } } }
Sample Input:
-190 -191 -192 -193 -194 195 196 197 198 199 200 0
Sample Output:
-190 = -1 x 2 x 5 x 19 -191 = -1 x 191 -192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3 -193 = -1 x 193 -194 = -1 x 2 x 97 195 = 3 x 5 x 13 196 = 2 x 2 x 7 x 7 197 = 197 198 = 2 x 3 x 3 x 11 199 = 199 200 = 2 x 2 x 2 x 5 x 5