← All coding problems
Sum of Primes in Ranges
mediumPlacement Coding+20 XPTime limit 2s
Answer q questions. Each question gives a range L R; print the sum of all prime numbers p with L ≤ p ≤ R (print 0 if there are none).
Input:
- line 1:
q - next
qlines:L R
Output: q lines — the sum for each range.
Constraints: 1 ≤ q ≤ 10⁵, 1 ≤ L ≤ R ≤ 10⁶. Sums can exceed 2³¹ — use 64-bit integers.
Think about it: testing every number of every range is far too slow. Build the Sieve of Eratosthenes once up to 10⁶, then a prefix-sum array pre[x] = sum of primes ≤ x. Each answer is pre[R] − pre[L − 1].
Sample input 1
3 1 10 10 20 14 16
Sample output 1
17 60 0
Sample input 2
1 2 2
Sample output 2
2
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).