Imapaj's blog

Number Theory True?
By Imapaj, history, 9 years ago, In English

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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I have a quection: how to check for O(logN) whether C is prime? Is there any deterministic way? Or just Millen-Rabin?

→ Reply