Hi Codeforces :P.
I'm trying to solve a problem about how many divisors has a Number.
In the Solutions Statements say that:
if we obtain only the factors of the number up to cube root of N.
then we obtain N = C*(factorization_of_N_up_to_cube_root)
and C can be only 1 or prime or prime*prime.
but i dont understand why.
Can see the entire explanation in the Presentation of the Solution, Problem F.
Presentation of Solutions|Problem F
I would greatly appreciate your help.
If C is prime*prime*prime (or more primes) then N >= C >= prime*prime*prime. It follows that one of those primes <= cubic root of N, a contradiction.
Thank you so much. :)
I have a quection: how to check for O(logN) whether C is prime? Is there any deterministic way? Or just Millen-Rabin?