Some hints please. My algo takes too much time.

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

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.

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

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

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.