Sieve of Eratosthenes
Find the sum of divisors of good numbers between L and R, such that a good number is square-free and the number of prime numbers dividing the sum of its divisors is prime.
Uptil 5 * 105, pre-compute for each number whether it is square-free, whether it is a prime number and its sum of divisors.
Use prefix sum to store the sum of divisors of all good numbers uptil i.
Answer for each test case = prefix_sum uptil [R] - prefix_sum uptil [L - 1]
Knowing the implementation of Sieve of Eratosthenes can be helpful in solving the problem. The sieve method can be used to find all prime numbers upto a certain integer N.
Square free numbers
Use a method similar to the Sieve of Eratosthenes.
Maintain a boolean array, in which if the ith index is marked true, then the integer i is square-free, else it is not.
For each integer, mark all multiples of its square as not-square-free. Hence, we are left with only square-free numbers.
- Counting divisors and sum of divisors
Consider a certain integer X - we know that X would be a proper divisor of the numbers X, 2*X, 3*X, …, K*X.
If the limit upto which we want to store divisors is Y, we know that K*X \le Y.
The implementation of this method is again similar to the Sieve of Eratosthenes.
- Good Numbers
For each integer i, we can compute whether it satisfies both conditions of a good number or not.
- Prefix Sum
To keep track of the sum of divisors of all good numbers uptil i, we store the cumulative sum of divisors of good numbers uptil i.
After all the pre-computation, we need to find out the sum of divisors of good numbers between L and R. For doing that, we used a standard prefix sum technique:
prefix_sum uptil [R] - prefix_sum uptil [L - 1]