Factor the Giant — Solution & Editorial

Back to the Problem

Trial division to √N (10⁹ steps) is too slow. Use Miller–Rabin to test primality and Pollard's rho to split composites recursively.

Complexity: O(n^1/4) per factor (expected)

Watch out: Semiprimes of two ~10⁹ primes are precisely the case where √N trial division dies — rho is required.