Prime's Sum Again
Time Limit : 3 Second
Memory Limit : 128 MB
- 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.
- 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.
- 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