×

# JMAGNUM , LOC2017 need help

 0 https://www.codechef.com/LOCSEP17/problems/JMAGNUM/ I got TLE on cases >10^3. Please someone help me understand the solution. asked 03 Oct '17, 14:31 3●2 accept rate: 0%

 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: https://www.codechef.com/viewsolution/15554267In 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 2.4k●7●22 accept rate: 20%
 1 3 precomputations will be needed. precompute all the primes first. O(nloglogn) 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. 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 585●4●14 accept rate: 8%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×301
×198
×30

question asked: 03 Oct '17, 14:31

question was seen: 249 times

last updated: 03 Oct '17, 20:08