Sum of Primes

4.3

23 votes
Easy, Number Theory
Problem

Let's define the function \(F(l,r)\) :

\( F(l,r) \) = \( \sum x\), \(\forall x \), where x is a prime number between l and r inclusive.

In Short, for each function \(F(l,r)\) you need to find the summation of all primes between the integers l and r inclusive.

Now, you shall be given multiple queries. In each query, you shall be given the integers l and r and you need to find the result of the function \(F(l,r)\)

Input Format:

The first line contains a single integer N denoting the number of queries. Each of the next N lines contains two integers l and r denoting the parameters of the \(i^{th}\) query.

Output Format:

For each query, output the answer on a new line.

Constraints

For \(30\) Points:

\( 1 \leq N \leq 1000 \)

\( 1 \leq l \leq r \leq 1000 \)

For the next \(70\) Points:

\( 1 \leq N \leq 5*10^5 \)

\( 1 \le l \le r \le 10^6 \)

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For the \(1^{st}\) query, the primes between 1 and 6 are 2, 3 and 5. Thus the answer= \(2 + 3 + 5\) = \(10\). Similarily, for the second query, Answer = \(5 + 7 + 11 + 13\) = \(36\).

Editor Image

?