I thought of solving it using segmented sieve. Like first I’ll calculate the prime factorisation of each number from l to r , then for each i’ll just multiply their powers of prime factor to get the total no. of factors of that number.
if total factors==3 then i’ll increament the ans else continue with the rest.
Can this approach be accepted? Or is there any better approach to solve it?
A couple of observations here can lead you to the solution.
First, factors of a number always exist in pairs. So the only case when the number of factors are odd is when there exists a pair in which both the numbers are same, that is, the number is a perfect square.
Also, since the resulting number also doesn’t have any other factors, it must be the square of a prime.
So you use a segmented sieve to generate primes till sqrt(1000000000000) = 10^6 and use it in all the queries to count the number of primes in the appropriate range.
in the same procedure of segment sieve create an array of vectors and make a look up table for each number(i.e for 6 factors are 1 2 3 and for 30 5*6 and 6 will return a vector of
size 3 which contains 1 2 3) while iterating through this array if you find the size of the vector corresponding to that index using unordered_map for the look up table might reduce the time complexity and decrease number of iteration
thankyou so much , it helps me in revising some basic theory of numbers.
got it bro, thanks
bro I tried this approach but where I’m going wrong? Could you please point out the mistake in my code- https://ideone.com/1XJSe9
In line 24, set
lli n = sqrt(i);
and it should work, although I’m almost sure it will TLE 
See if you can optimise the search for count of such primes.
Precompute a sorted list of primes, use binary search to find the primes within range sqrt(l) and sqrt(r) for each query. This reduces the complexity of each query from O(N) (where N is r - l + 1) to O(log(n)) (where n is the number of primes till 10^6)