Subtask 1

For the first subtask, we can just brute force each query and find all the primes in the range given and also accumulate the sum when we find them. The intended was to use prime checking functions of square root time complexity. Each query can be answered in ~\mathcal O(K \max\{\sqrt{p_i}\})~ time, where ~p_i~ is the ~i^\text{th}~ prime in the range given.

Time Complexity: ~\mathcal O(QK \max\{\sqrt{p_i}\})~

Subtask 2

For the second subtask, we need to do some preprocessing. First, we can preprocess primes up to a certain number ~X~ and store them into an ArrayList or array.

The value of ~X~ can be found with the following:

An approximation for the number of primes under an integer ~n~ is ~\dfrac{n}{\ln n - 1}~. Given the maximum ~x~ to be ~10^5~, we get around ~\dfrac{10^5}{\ln 10^5 - 1} \approx 9\,512~ primes under ~10^5~. In fact, there are ~9\,562~ primes under ~10^5~. Since we are looking at the next ~k~ primes after, with the maximum value of ~k~ being ~10^4~, we get ~9\,512 + 10^4 = 19\,512~ as the number of primes we need to preprocess and store.

Using this number, we use the approximation to get ~\dfrac{X}{\ln X - 1} = 19\,512~, ~X \approx 226\,000~. We can then use prime checking functions and preprocess all the primes up to ~2.3 \times 10^5~ in ~\mathcal O(X \sqrt X)~ or ~\mathcal O(X \log(\log X))~ time.

Then using the preprocessed array, we can then create a prefix sum array of the array; this will take ~\mathcal O(X)~ time.

For each query, we can binary search for the index ~l~ in our preprocessed array which has the smallest prime greater than or equal to ~x~. Alternatively, we can precompute the number of primes strictly less than each integer from ~1~ to ~10^5~ using a second prefix sum array, allowing ~l~ to be queried for in ~\mathcal O(1)~ time. This solves the first part of the query. Then we can use our first preprocessed prefix sum array to quickly get the sum of all primes from index ~l~ to ~l+k~ in ~\mathcal O(1)~ time, solving the second part of the query.

Time Complexity: ~\mathcal O(X \sqrt X + Q \log X)~, ~\mathcal O(X \log(\log X) + Q \log X)~, ~\mathcal O(X \log(\log X) + Q)~, or similar, depending on implementation.