Difficulty : Challenge
Pre-requisites : prime factorisation, pollard-rho heuristics
The problem requires nothing more than but factorizing the integer number, as it is stated in the statement.
The basic approach is the following:
- First, we determine, whether the given integer is smaller than 1018;
- If it’s so, we can use long long data type, that is faster and simpler to use. We can brute-force all the primes not greater than 106 and check whether they divide the given integer or not. After we divide the given number by all its’ divisors not greater than 106, it will be either 1, either a prime, either a product of two large primes.
- If the number is actually greater than 1018, we should use bignums arithmetic. That means that all the operations become slower than in the long long case, so we can brute force all the prime divisors smaller than some constant that can be figured out by experiments, depending of the speed of the solution.
This solution is easy to code, but it also has some obvious disadvantages. Moreover, at the cases if the second type this approach won’t work at all, because the test cases of the second type are basically a product of two big primes.
In order to make this solution better, there are two ways. At first, you should speed the bignum arithmetic up as much as possible. At second, you can consider using some better methods. For example, Pollard-Rho. A lot of the information on non-trivial factorization algorithms can be actually found on the internet.
At the end, I’d like to note that it seems best to solve the 4-th group, rather than other ones. Even the brute-force solution is capable of finding a hundred divisors for the test of the fourth group.
Setter’s solution: link
Tester’s solution: link