sum-of-primes-7

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 ≤q N ≤q 1000  

 1 ≤q l ≤q r ≤q 1000 

For the next 70 Points:

 1 ≤q N ≤q 5*10^5  

 1 ≤ l ≤ r ≤ 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.

Source: hackerearth | Difficulty: EASY
Tags: Number theory


Solutions:
__author__ = 'Admin'

limit = 1000001
list_of_primes = []
for i in range(0 , limit):
	list_of_primes.append(0)
i= 2
while(i * i <= limit-1):
	if list_of_primes[i] == 0:
		k = 2
		j = i * k
		while(j <=limit-1):
			list_of_primes[j] = 1
			k = k + 1
			j = i * k
	i = i + 1
# print list_of_primes
total = 0
for i in range(2 , limit):
	if list_of_primes[i] == 0:
		total = total + i
		list_of_primes[i] = total
	else:
		list_of_primes[i] = list_of_primes[i-1]
nq = int(input())
for t in range(0 , nq):
	inp = list(map(int , input().split()))
	l = inp[0]
	r = inp[1]
	print(list_of_primes[r] - list_of_primes[l-1])