1205 - Primes' Sum

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 324

Solved: 82

Description
As is known to all, a prime number is a number who can only be divided by 1 and itself. For example, 2,3,5 are all prime numbers but 4,6 are not.

Because 4 has another diviser 2, and 6 has two divisers: 2 and 3.

Now the problem is, give you two non-negetive integers, start and end, your work is to tell me the sum of all the prime numbers between start and end(include the start and end).

Input
The first line is an integer T, which means the test cases in the input file, T is no more than 100000

The 2nd to the (T+1)th lines are the cases, for each line, there are two integers start and end, both of them are larger than 0 and smaller than 100000.

Output
For each test case, output one integer for a line, the sum of all the prime numbers in the range.

sample input
3

1 10

4 6

14 17

sample output
17

5

17

hint
Huge input file, scanf is recommended.
source
Sempr
© 2015 HUST ACMICPC TEAM. All Right Reserved.