 # Help anyone?

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.

2 Likes

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

1 Like

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.

Hint

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)