Contest1201/I.java

import java.util.Scanner;

public class I {
    static int primers[] = new int[3600];

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            int n = cin.nextInt();
            System.out.print(n + "=");
            init();
            if (n < 2) {
                System.out.print(n);
            } else {
                for (int i = 0; i <= 3600; i++) {
                    if (n % primers[i] == 0) {
                        System.out.print(primers[i]);
                        n /= primers[i];
                        break;
                    }
                }
                for (int i = 0; i < 3600; ) {
                    if (n % primers[i] == 0) {
                        System.out.print("*" + primers[i]);
                        n /= primers[i];
                    } else i++;
                }

            }
            System.out.println();
        }
        cin.close();
    }

    private static void init() {
        int index = 0;
        for (int i = 2; index < 3600; i++) {
            if (isPrime(i))
                primers[index++] = i;

        }
    }

    private static boolean isPrime(int n) {
        if (n < 2) return false;
        if (n % 2 == 0 && n != 2) return false;
        for (int i = 3; i * i <= n; i += 2)
            if (n % i == 0)
                return false;
        return true;
    }
}