JDCC '16 Contest 4 P3 - Big Integer Factorization

View as PDF

Submit solution


Points: 7
Time limit: 2.0s
Java 5.0s
Python 6.0s
Memory limit: 64M

Author:
Problem type

It is a well-known fact that every natural number has a unique prime factorization. That is, you can uniquely express each natural number \(N\) as:

\[ N = P_1^{M_1} \times P_2^{M_2} \times \ldots \times P_K^{M_K} \]

Where \(P_1 < P_2 < \ldots < P_K\) are prime numbers. For example, \(28 = 22 \times 7\) and \(3645 = 36 \times 5\).

In general, finding the prime factorization of large numbers is difficult to do (and serves as a basis for many cryptographic systems). However, in some special cases it is easy to find a number’s prime factorization.

One such case is when a number is a power of a smaller number. Given a number \(N\), can you figure out the prime factorization of \(N^N\)?

Input

Each test case contains one integer \(N\ (2 \le N \le 2^{47})\).

Output

For each test case, output, on one line, the prime factorization of the number.

Sample Input

6

Sample Output

2^6 * 3^6

Sample Input

197538393501504

Sample Output

2^1185230361009024 * 3^790153574006016 * 11^592615180504512 * 31^987691967507520

Comments

There are no comments at the moment.