How do you solve this problem ?

Posted by

rohit 25 Sep 2011 01:12

Some hints please. My algo takes too much time.

Re: How do you solve this problem ?

You need factoring N by numbers 2..10^6. If after factoring N>1 and N not prime, then your N=p*q, where p and q - prime numbers.

*Edited by author 27.09.2011 16:46*

Re: How do you solve this problem ?

Posted by

svr 10 Oct 2011 14:33

most difficult case n=p*p, where p- is prime

for it case quick _int64 sqrt(__int64 n) function is needed,

in other cases there is a factor of n which is <1000000.

Re: How do you solve this problem ?

svr what should be the output when n = p*p where p is prime ??

i guess just n ? becuase n is already odd and its the maximum ?

*Edited by author 19.01.2015 01:04*

Re: How do you solve this problem ?

I just did straight forward factorization (with rho) of an input number and then divided it by primes that have an odd power in factorization.

0.31 ms, 1400 kb.

*Edited by author 08.07.2018 18:21*

Re: How do you solve this problem ?

AC in 0.015 (in plain C) with something much simpler than RHO.

- start factorizing the simplest way they teach you in the kindergarten

- when the test reach large values, check if the reminder has a perfect square

-- if so - return the square and count as it is a prime divisor ^2

(because even if it can be factorized, it will be an amount of multipliers ^2)

-- if no - stop checking

(because the reminders are obviously large prime values ^1 and can be ignored)

- multiply all primes with even powers * primers with odd powers (n) >= 3 with power n-1

I bet it can be accepted in 0.001 if Intel C 7 was still a compiler option.