count the integers which are not divisible by a perfect square.

Recently I came across this question in a coding contest:

Given two integers x,y. Print the count of numbers in between x and y which are not divisible by a perfect square

1 <= x,y <= 10^9

0 <= |x-y| <= 10^6

what is the approach for this type of questions?

Could you give a few more details such as the limits of x and y. The first approach that comes to my head is to use sieve of Eratosthenes. Only difference is that instead of eliminating multiples of prime numbers we eliminate multiples of perfect squares. If x and y are very large but y-x is of acceptable size (around 10^5 -10^6) then you can use a segmented sieve like approach for this.

1 <= x,y <= 10^9,

0 <= |x-y| <= 10^6

As i said, the range |y-x|is limited. This looks like a direct question based on the sieve algorithm i mentioned above.

//