bzoj1225.java

import java.util.; import java.math.;

class Main { static int n, m, a[], tp, pn[]; static BigInteger f[][]; static boolean pr[], fl[][];

static void pre() {
	int maxm = 30;
	pr = new boolean[maxm];
	pn = new int[maxm];
	pn[0] = 1;
	tp = 1;
	for (int i = 0; i < maxm; ++ i)
		pr[i] = false;
	for (int i = 2; i < maxm; ++ i) {
		if (!pr[i])
			pn[tp ++] = i;
		for (int j = 1; j < tp && i * pn[j] < maxm; ++ j) {
			pr[i * pn[j]] = true;
			if (i % pn[j] == 0)
				break;
		}
	}
}

public static void main(String args[]) {
	Scanner cin = new Scanner(System.in);
	pre();
	m = cin.nextInt();
	a = new int[309];
	n = 0;
	for (int i = 1; i * i <= m; ++ i)
		if (m % i == 0) {
			a[n ++] = i;
			if (i * i < m)
				a[n ++] = m / i;
		}
	Arrays.sort(a, 0, n);
	f = new BigInteger[n][];
	fl = new boolean[n][];
	for (int i = 0; i < n; ++ i) {
		f[i] = new BigInteger[tp];
		fl[i] = new boolean[tp];
		for (int j = 0; j < tp; ++ j) {
			f[i][j] = BigInteger.valueOf(0);
			fl[i][j] = false;
		}
	}
	fl[0][0] = true;
	f[0][0] = BigInteger.valueOf(1);
	for (int i = 1; i < n; ++ i)
		for (int j = 1; j < tp; ++ j) {
			fl[i][j] = true;
			f[i][j] = BigInteger.valueOf(pn[j]).pow(a[i] - 1);
			for (int k = 0; k < i; ++ k)
				if (fl[k][j - 1] && a[i] % a[k] == 0) {
					BigInteger tmp = f[k][j - 1].multiply(BigInteger.valueOf(pn[j]).pow(a[i] / a[k] - 1));
					if (f[i][j].compareTo(tmp) > 0)
						f[i][j] = tmp;
				}
		}
	BigInteger ans = f[n - 1][1];
	for (int i = 2; i < tp; ++ i) {
		if (fl[n - 1][i] && ans.compareTo(f[n - 1][i]) > 0)
			ans = f[n - 1][i];
	}
	System.out.println(ans.toString());
}

}