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


JMAGNUM , LOC2017 need help I got TLE on cases >10^3. Please someone help me understand the solution.

asked 03 Oct '17, 14:31

mysterion's gravatar image

accept rate: 0%

You can use a sieve and for each prime, instead of just using a flag to mark it as prime or not, you can store the sum of the prime divisors. After that you can take the prefix sum to answer each test case in O(1).
My solution:
In my solution, initially ans[i] stores the sum of digits of prime divisors of i, then I take the prefix sum in the second loop. isprime[i]==1 if i is prime else 0.


answered 03 Oct '17, 14:37

ista2000's gravatar image

4★ista2000 ♦
accept rate: 20%

edited 03 Oct '17, 16:03

3 precomputations will be needed.

  1. precompute all the primes first. O(nloglogn)

  2. then precompute the sum of digits for every prime. precomuptation will take O(logn) for every prime number that you have already calculated from the sieve above.

  3. then precompute your ans for every query from 0 to i.. and then just print ans[r]-ans[l-1].

well written code : CODE


answered 03 Oct '17, 14:36

goyal_banna's gravatar image

accept rate: 8%

edited 03 Oct '17, 14:37

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 03 Oct '17, 14:31

question was seen: 249 times

last updated: 03 Oct '17, 20:08