由于两个数字 X 和是，发现是无平方数的计数，其中无平方数是整除没有完美的广场上，除了 1 。例如， 10 是方形的，免费的，但 18 不是，因为它是整除 9 = 32 。一些积极广场的免费电话号码是：

Given two numbers x and y , find count of numbers that are squarefree where squarefree number is one divisible by no perfect square, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32. Few positive square-free numbers are :

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15 ...

限制

1 <= X,Y <= 10^9

0 <= |X-Y| <= 10^6

x=10 , Y=15 

给

ans=5

我的做法是生成所有素，直到平方根（10 ^ 9）（埃拉托色尼筛），并检查是否每个数字在给定范围内整除主要广场。伯爵这样的数字是从范围长度减去给方免费电话号码。

My approach is to generate all prime till squareroot(10^9) (sieve of eratosthenes), and check whether each number in given range divisible by square of prime . Count of such numbers is substracted from length of range to give square free numbers .

但这种方法超时的复杂性，请提出了一些其他的方法

But this approach time out in complexity , please suggest some other approach

推荐答案

使用容斥原理：

让 F（N）= 1的非方形免费电话号码... N 。我们将仅做素数的平方容斥，从而避免超量为正方形的平方

Let f(n) = number of non-square-free numbers in 1 ... n. We will only do inclusion-exclusion on the squares of primes, so as to avoid overcounting for squares of squares.

我们有：

f(n) = n / 4      => these are divisible by 4, so NOT square-free
       +
       n / 9      => these are divisible by 9, so NOT square-free
       + 
       n / 25     => these are divisible by 16, so NOT square-free
       +
       ...
       -
       n / (4*9)  => these are divisible by both 4 and 9, so we overcounted
       -
       n / (4*25) => these are divisible by both 4 and 25, so we overcounted 
       -
       ...

如何有效的是什么？

How efficient is this?

我们只需要素数 P ，使得点^ 2'= 10 ^ 9 ，这意味着 P＆LT; 31623 。这已经不是很多素数，任何微不足道的筛（或者甚至审判庭）要足够快。然后应用容斥，这也将是快速的，因为平方素数的产品将获得较大的快，所以你就可以pmaturely终止$ P $在AA很多情况下（的N /某事= 0 每当的东西和GT; N ）

We only need primes p such that p^2 <= 10^9, meaning p < 31623. This already isn't a lot of primes, any trivial sieve (or maybe even trial division) should be fast enough. Then apply inclusion-exclusion, which will also be fast since the products of squared primes will get large fast so you'll be able to terminate prematurely in a a lot of cases (n / something = 0 whenever something > n).

为了明白为什么你就可以终止prematurely，改写上面：

In order to see why you'll be able to terminate prematurely, rewrite the above as:

f(n) = n / (2^2) -
       n / (2^2*3^2) +
       n / (2^2*3^2*5^2) -  <= this becomes 0 very fast. 
                               When it does, 
                               backtrack and increment the previous term.
                               For example, if this were 0,
                               you'd do - n / (2^2*5^2) next
       ...

在此这里更多信息。