问需要帮助在时间复杂度方面有效地解决以下问题

EN

首先，更容易限制问题，忽略下限(即:处理L=1)。如果我们可以计数任何N都可以被素数<= N整除的数，我们也可以通过从计数<= R中减去数字<= L-1的计数间隔来计数它们。

给定任意数x，可被x整除的数<= R的计数为零(R/ x)。

现在，我们可以应用包容排除原则来获得结果。首先，我将手工显示3个素数p1、p2和p3的结果，然后给出一般的结果。

<= R可被p1、p2或p3整除的数字计数为：

R / p1 + R / p2 + R / p3
- R / (p1p2) - R / (p1p3) - R / (p2p3)
+ R / (p1p2p3)

(这里假定/是整数平方除法)。

一般情况如下：

sum((-1)^(|S|+1) * R / prod(S) for S a non-empty subset of {p1, p2, .., pN}).

在这里，S覆盖素数的所有子集，prod(S)是子集中素数的乘积，初始项在-1和+1之间变化，这取决于子集的大小。

针对您的问题，N<=10，所以有1023个非空子集需要迭代。

下面是一些Python代码示例：

from itertools import *

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def prod(ns):
    r = 1
    for n in ns:
        r *= n
    return r

def divs(primes, N):
    r = 0
    for S in powerset(primes):
        if not S: continue
        sign = 1 if len(S) % 2 else -1
        r += sign * (N // prod(S))
    return r

def divs_in_range(primes, L, R):
    return divs(primes, R) - divs(primes, L-1)

请注意，该代码的运行时间或多或少取决于素数，而不是L和R的大小。

假设n是区间大小，N是const。

对于每个素数p，在可被素数整除的区间中应该有粗略的(R-L) / p数。

求第一个可在区间内被p整除的数: L‘= by +m(p-L% p)。

如果L‘> R，则没有，否则就有1+地板((R’) / p).

例子:3，10，20

L‘= 10 +3-10%3=12。

区间内可被3除的数:1+地板((20-12) / 3) =3

注意:到目前为止，我们还没有使用p1..pN是素数的事实。

剩下的问题似乎是:如何避免计数一个可被多个素数多次整除的数字？假设我们有3,5和10，20，我们需要避免数15两次.

也许我们可以用上面的计数算法来计算(p1*p2)等的可分性，并相应地减少总数？如果N是const，这应该仍然是const时间。因为p1...pN是素数，所以它们的所有产品都需要不同(因为任何数字都不能有多个素因式分解)。