spoj problem


how do i solve this question. i need to find whether sum of all divisors of a number is a prime number or not.I am not able to think of any optimised solution keeping the constraints in mind.




@michelangelo…i observed that if no. if a perfect square answer is yes. the only exception is the number 2.But it gives wrong answer


but if i store all perfect squares and start finding their sum of divisors and then check if it is prime or not, it will give tle as the sum of divisors for 10^6 would be quite big. And i’ll have to check if that no… is prime which again will involve loping


There is a pattern for the solution. Write the first few numbers that satisfy the given constraints and you’ll be good to go.


36, 49, 81, and many more perfect squares do not satisfy that property. The trick is to reduce the solution space to perfect squares and then apply the given conditions to get the final solution. Of course, the exception being 2.