Factor the Giant

Difficulty: 2300 6000 ms 128 MB

number-theory pollard-rho

Print the prime factorization of N (up to 10¹⁸) in increasing prime order, formatted like 2^3 7 13^2 (exponent 1 omitted).

Input: one integer N.

Output: the factorization, or 1 when N = 1.

Constraints:

• 1 ≤ N ≤ 10¹⁸

Sample Tests

360

2^3 3^2 5

1

1

Read the Editorial