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*