Editorial for BSSPC '21 J5 - James and the Euclid Test


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: sushi

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.


Comments

There are no comments at the moment.