Description

对于任意输入的正整数n，请编程求出具有n个不同因子的最小正整数m。例如：n=4，则m=6，因为6有4个不同整数因子1，2，3，6；而且是最小的有4个因子的整数。

Input

n（1≤n≤50000）

Output

m

Sample Input

4

Sample Output

6

题解

这道题和解题思路和方法简直一毛一样...

同样我们引入这个公式：

对任一整数$a＞1$，有$a={p_1}^{a_1}{p_2}^{a_2}…{p_n}^{a_n}$，其中$p_1<p_2<…<p_n$均为素数，而$a_1$,$a_2$…,$a_n$是正整数。

$a$的正约数个数为：$(1+a_1)(1+a_2)…(1+a_n)$

同理，我们也是求有$n$个因数的最小整数。

我们最坏的情况所有质数只取$1$个，由于$15<log_{2}50000<16$

所以只要取前$16$个质数即可，

其余都和之前那题一样...

搜的时候为了保存最优值，因为数据大会爆$long$ $long$我们考虑用指数幂的形式保存，带一个数组保存取质数的个数。

同时注意每层循环枚举取质数的个数时候，因为不合法的情况很多，可以只枚举$\sqrt n$次，然后用枚举的值算出对应的另外一个值。

1 #include
     
       2 #include