algorithm - 范围内的 squarefree 数字计数

Question

给定两个数字 x 和 y ，找到无平方数的数字计数，其中无平方数可以被任何完全平方数整除，1 除外>。例如，10 是无平方的，但 18 不是，因为它可以被 9 = 32 整除。很少有无平方正数是:

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

使用 inclusion-exclusion principle :

让f(n) = number of non-square-free numbers in 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
       ...

关于此的更多信息 here .