I have a number n (0 < n < 2 * 10^18), and I am given that it has exactly 4 divisors.

Is there a way I could get those divisors faster than O(sqrt(n)) ?

Using a classical algorithm to find divisors of a number (link) takes O(sqrt(n)) time. sqrt(2*10^18) is around 10^9 and it would take too much time.

Also a number with exactly 4 divisors is a product of two different prime numbers, or a cube of a prime number.

CodePudding user response：

Pollard's rho method is simple, and has takes expected O(sqrt(sqrt(n)) time. sqrt(sqrt(10¹⁸)) is < 32000, so quite fast for numbers in that range.

CodePudding user response：

Big O gives you the complexity of the algorithm. It doesn't give you the amount of time it takes to calculate it.

If your number is 10^18, an O(sqrt(n)) algorithm doesn't take 10^9 seconds to complete. It'll take ~10^9 iterations to complete.

CPUs are very fast. They can execute 10^9 instructions per second.

Factoring the 18 digit number 600851475143123457 into the factors 3, 11 and 18207620458882529 in C# took 720ms and 480ms in C (not multithreaded, Ryzen 7 CPU, Release builds). Please specify how that "would take too much time." What performance requirements do you have?