You are not logged in. Please login at www.codechef.com to post your questions!

×

spoj problem

http://www.spoj.com/problems/ABA12D/
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.

asked 19 Jul '14, 19:11

aman2192's gravatar image

1★aman2192
123
accept rate: 0%

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

(19 Jul '14, 19:30) michelangelo4★

thanks....

link

answered 19 Jul '14, 19:46

aman2192's gravatar image

1★aman2192
123
accept rate: 0%

@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

link

answered 19 Jul '14, 20:04

aman2192's gravatar image

1★aman2192
123
accept rate: 0%

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.

(19 Jul '14, 20:15) michelangelo4★

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

link

answered 19 Jul '14, 21:11

aman2192's gravatar image

1★aman2192
123
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×18

question asked: 19 Jul '14, 19:11

question was seen: 4,023 times

last updated: 23 Oct '14, 18:03