Limits 1s, 512 MB

Given an integer NN, can you determine its prime factors?

Input

The input will contain a single integer NN (2N1062 \le N \le 10^6).

Output

Print the prime factors of NN in the following format:

N = f1 ^ p1 * f2 ^ p2 * f3 ^ p3 ...

For example, when N=20580N = 20580, you will print:

20580 = 2 ^ 2 * 3 ^ 1 * 5 ^ 1 * 7 ^ 3

Note that the prime factors are in ascending order. If a prime number is not a prime factor of NN, then the prime number is omitted from the expression.

Sample

InputOutput
20580
20580 = 2 ^ 2 * 3 ^ 1 * 5 ^ 1 * 7 ^ 3

Submit

Login to submit.

Statistics

87% Solution Ratio
spybitEarliest, Nov '22
user.2599Fastest, 0.0s
habijabiLightest, 4.9 MB
raselrokyShortest, 231B
Toph uses cookies. By continuing you agree to our Cookie Policy.