范围内squarefree数的计数

Question

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

我的方法是生成所有素数直到squareroot(10^9)（埃拉托色尼筛），并检查给定范围内的每个数是否可被素数的平方整除。这些数字的计数从范围的长度中减去，以给出平方自由数。

但是这种方法在复杂度上超时了，请建议一些其他的方法

Answer 1

使用包含-排除原则：

设f(n)=1...n中非平方自由数的个数。我们只在素数的平方上做包含-排除，以避免对平方的平方进行超算。

我们有：

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 
       -
       ...

这样的效率有多高？

我们只需要素数p，这样p^2<=10^9，意思是p<31623。这已经不是很多素数，任何琐碎的筛子（甚至可能是试除）都应该足够快。然后应用包含-排除，这也会很快，因为平方素数的乘积会很快变大，所以在很多情况下可以过早终止(n/something=0，每当something>n)。

为了了解您为什么能够过早终止，请将上面的内容改写为：

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
       ...