Count and add up primes in many ranges (sieve + prefix sums)

• The Sieve of Eratosthenes marks every composite up to N in O(N log log N).
• Prefix arrays turn each query into two lookups: cnt[R] − cnt[L−1].
• The sum of all primes up to 10^6 is larger than 2^31, so use 64-bit integers.

1. Sieve up to N = max R. Start by assuming everything from 2 upwards is prime. For each i with i * i ≤ N that is still marked prime, mark i*i, i*i + i, … as composite. Start at i*i because smaller multiples were already marked by smaller primes. The total work is O(N log log N).

2. Prefix arrays. cnt[x] = number of primes ≤ x, and sum[x] = sum of primes ≤ x. Each is built in one pass.

3. Each query is cnt[R] − cnt[L−1] and sum[R] − sum[L−1], which is O(1).

The total is O(N log log N + Q), compared with O(Q · range · √R) for trial division, which is hopeless at these limits.

Pitfalls

• 1 is not prime. Mark 0 and 1 before sieving.
• The sum of primes below 10^6 is about 3.7 × 10^10, which overflows a 32-bit int. Use long long in C++. In JavaScript a Number holds integers exactly up to 2^53, which is enough.
• Memory: a byte array of size 10^6 is about 1 MB. A bitset makes it 8 times smaller.

Follow-up: for ranges near 10^12 you cannot sieve all the way up. A segmented sieve uses the primes up to √R to sieve only the window [L, R].