题目描述

唯一分解定理指出，对于每个大于 $1$ 的自然数 $n$，如果 $n$ 不是质数，那么 $n$ 可以唯一分解为有限个素数的乘积。即存在素数 $p_1,p_2,…,p_k$ 和正整数 $a_1,a_2,…,a_k$，使得：

$$n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k} $$

例如: $100=2^2\times 5^2$

现要求编写程序实现因数分解的过程

输入格式

输入一个正整数 $n$。

输出格式

按格式输出质因数分解过程

10

2^1 5^1

16

2^4

34

2^1 17^1

数据规模与约定

• 对于 $30\%$ 的数据，$2 \le n \le 10^3$。

• 对于 $100\%$ 的数据，$2 \le n \le 10^{14}$。