All Tracks Math Number Theory Basic Number Theory-2 Problem

Sum of Primes
Tag(s):

Easy-Medium, Number Theory

Problem
Editorial
Analytics

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 \)

SAMPLE INPUT
2
1 6
4 13
SAMPLE OUTPUT
10
36
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\).

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Уведомления
View All Notifications

?