PROBLEM LINK:
Author: Saumyajit Dey
Tester: Devamanyu Hazarika
Editorialist: Devamanyu Hazarika
DIFFICULTY:
EASY
PREREQUISITES:
Math
PROBLEM:
The problem states that all the numbers which have exactly two divisors (greater than 1) have been deleted. Now ,you have to answer the count of missing numbers in a given range.
EXPLANATION:
We can easily figure out that a number is marked as many times as the divisors(greater than 1) of that number.
Now all missing numbers are basically square of prime numbers which will have only two divisors that is itself and its square root.
The task remains to identify the count of such numbers in a given a range. This can be easily done by generating prime numbers upto 105 using “Seive of Erastosthenes” and then squaring the prime numbers to get square of primes.
Now given any query, we can use binary search to find the indices of the smallest and largest square primes that lie in the given range (let it be i and j). Then the answer for the query will be j-i+1. Time complexity for each query is O(logk), where k is the number of square primes upto 109, which comes up to be in the order of 4 * 104.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.