emma-and-the-prime-sum

Emma is fond of prime numbers. Emma’s teacher gave her an interesting problem to solve. 
The problem is as follows:
The teacher gave Emma 2 positive integers x and y(x ≤ y). 
She asked Emma to find the sum of all the prime numbers between x and y(x and y inclusive).
The teacher gave Emma a few such pairs to calculate the required sum. 
The values of x and y were large and she could not do this task manually, so, Emma came to you 
for help to calculate her answers using a program.
Your task is to help Emma.

INPUT
The first line of input contains the number of test cases, t. 
Then, t lines follow, each containing 2 positive integers x and y, for which you have to find the required sum. 

OUTPUT
The output contains t lines each contains the required sum for that particular test case.
CONSTRAINTS
1 ≤ t ≤ 100000
1 ≤ x ≤ y ≤ 10^6

SAMPLE INPUT
3
1 10
2 6
5 10

SAMPLE OUTPUT
17
10
12

Source: hackerearth | Difficulty: EASY


Solutions:
__author__ = 'Admin'
nq = int(input())
arr = []
for i in range(0 , 1000002):
	arr.append(0)

arr[1] = 1

for i in range(2 , 1000002):
	if i*i <=1000001:
		if arr[i] == 0:
			k = 2
			j = i*k
			while(j <= 1000001):
				arr[j] = 1
				k = k + 1
				j = i*k

ans = 0
for i in range(1 , 1000002):
	if(arr[i] == 0):
		ans = ans + i
		arr[i] = ans
	else:
		arr[i] = arr[i-1]
for q in range(0,nq):
	inp = list(map(int , input().split()))
	x = inp[0]
	y = inp[1]
	if(arr[y] == arr[x-1]):
		print(0)
	else:
		print(arr[y]-arr[x-1])