Sum of Primes 2

View as PDF
Submit solution
Points: 5 (partial)
Time limit: 0.6s
Memory limit: 64M
Author:
alextxu
Problem type

Bob needs to do a lot of practice with prime numbers for homework. Being a curious student, he will ask you Q questions. Each of these questions will be of the form: what is the sum of all prime numbers between A and B (inclusive)?

Input Specification

The first line contains a single integer: Q

Each of the next Q lines contains two space-separated integers: A, B

Output Specification

Output the answer to each question on a separate line.

Constraints

1 \le Q \le 10^5

1 \le A \le B \le 10^5

Subtasks

Subtask 1 [20%]

1 \le Q \le 1000

1 \le A \le B \le 1000

Subtask 2 [80%]

No additional constraints.

Sample Input

3
1 2
5 11
3 19

Sample Output

2
23
75

Comments


  • 0
    Kiki_Delfin  commented on Aug. 5, 2025, 2:53 p.m.

    how to dont get TLE?


    • 1
      Another_User  commented on Aug. 24, 2025, 4:30 a.m.

      Precompute the primes using Sieve of Eratosthenes while keeping track of the sum in a prefix sum array. Then answer the queries.


  • 0
    equ121  commented on Dec. 20, 2024, 2:53 a.m.

    true but pointless...


  • 0
    EricBrazhnyk  commented on April 13, 2024, 6:37 a.m.

    is it possible not to TLE on C# for this question


    • 0
      stanwww  commented on Oct. 29, 2024, 8:38 p.m.

      Use sieve of eratosthenes.


  • 1
    henrybaolol9  commented on Feb. 7, 2021, 1:31 a.m.

    why am i getting array index out of bounds exception?


    • 2
      AQT  commented on Feb. 7, 2021, 5:45 a.m.

      Possible overflow on line 25


    • 7
      thomas_li  commented on Feb. 7, 2021, 1:43 a.m.

      It is because your array index is out of bounds.


      • 0
        kevinyang  commented on Feb. 7, 2021, 4:00 a.m.

        very true actually orz