Skills101
← 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 q lines: 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).

Loading editor…

Log in to run and submit your code — it's free.