Editorial for BSSPC '21 J5 - James and the Euclid Test
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 time, where is the prime in the range given.
Time Complexity:
Subtask 2
For the second subtask, we need to do some preprocessing. First, we can preprocess primes up to a certain number and store them into an ArrayList or array.
The value of can be found with the following:
An approximation for the number of primes under an integer is . Given the maximum to be , we get around primes under . In fact, there are primes under . Since we are looking at the next primes after, with the maximum value of being , we get as the number of primes we need to preprocess and store.
Using this number, we use the approximation to get , . We can then use prime checking functions and preprocess all the primes up to in or time.
Then using the preprocessed array, we can then create a prefix sum array of the array; this will take time.
For each query, we can binary search for the index in our preprocessed array which has the smallest prime greater than or equal to . Alternatively, we can precompute the number of primes strictly less than each integer from to using a second prefix sum array, allowing to be queried for in 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 to in time, solving the second part of the query.
Time Complexity: , , , or similar, depending on implementation.
Comments