#G1020. [GESP202309 五级] 因数分解

[GESP202309 五级] 因数分解

[GESP202309 五级] 因数分解

题目描述

每个正整数都可以分解成素数的乘积,例如:6=2×36 = 2 \times 3、20=22×520 = 2^2 \times 5。

现在,给定一个正整数 NN,请按要求输出它的因数分解式。

输入格式

输入第一行,包含一个正整数 NN。约定 2≤N≤10122 \leq N \leq 10^{12}。

输出格式

输出一行,为 NN 的因数分解式。要求按质因数由小到大排列,乘号用星号 * 表示,且左右各空一格。当且仅当一个素数出现多次时,将它们合并为指数形式,用上箭头 ^ 表示,且左右不空格。

样例 #1

样例输入 #1

6

样例输出 #1

2 * 3

样例 #2

样例输入 #2

20

样例输出 #2

2^2 * 5

样例 #3

样例输入 #3

23

样例输出 #3

23

数据范围

  • 2≤N≤10122 \leq N \leq 10^{12}。