范围内无平方数的计数

Question

给出两个数字,x并y找到无数字的数字,其中squarefree数是一个可被除尽的完美正方形除外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)(eratosthenes的筛子),并检查给定范围内的每个数字是否可被素数平方整除.从范围长度中减去这些数字的数量,得到平方自由数.

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

Answer 1

使用包含 - 排除原则:

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

在此更多信息在这里.