HUST Past Monthly Hard Problems Challenge Contest (1)

From: 2011-05-13 12:00:00 To: 2011-05-13 17:00:00 Now: 2017-09-20 01:10:07 Status: Public

F - Prime's Sum Again

Time Limit: 3s Memory Limit: 128MB

Submissions: 118 Solved: 18
Description
As is known to all, a prime number is a number which can only be divided by 1 and itself. For example: 2, 3 and 5 are all prime numbers but 4 and 6 are not, because 4 has another divisor 2, and 6 has two other divisors 2 and 3. Then the problem is: give you two nonnegative integers L and R, you are asked to tell me the sum of all the prime numbers in the range [L, R). Range [L, R) means all the integers x that L <= x < R.
Input
The first line is an integer T (T <= 200) means the number of the test cases. The following T lines are the T test cases. For each line, there are two integers L and R, 0 <= L, R <= 1,000,000,000.
Output
For each test case, output a single line with the sum of all the prime numbers in the range [L, R), because the sum is too large, you can only output the last 4 digits of the sum.
Sample Input
```3
1 10
4 6
14 18
```
Sample Output
```0017
0005
0017
```
Hint
Source