python - 解决这个难题的最佳算法是什么？

Question

所以我遇到了这个问题:

1到1000之间有多少个数不能被数字2、3、5整除？

一开始看起来很简单，所以我写了一个快速的 python 程序来解决它:

count = 0
for number in range(1,1000):
    if number % 2 != 0 and number % 3 != 0 and number % 5 != 0:
        count += 1
print(count)

我得到了正确答案 (266)，但我认为如果我想检查的不仅仅是 3 个值，那么这样做需要大量输入。我也想做一个数学解决方案，所以我遇到了这个:

1000 - ((1000/2 +1000/3 +1000/5) -(1000/2x3 +1000/2x5 + 1000/3x5)+ (1000/2x3x5)) = 1000-((500+ 333+200) - (166 +100 + 66) + 33) = 1000- 734 = 266

我认为这是一个很好的方法，所以我在代码中实现了它:

def foo(ln = 1000), numbers = [2,3,5]:
    div = 0
    muldiv = 0
    totdiv = 1


    for n in numbers:
        div += ln/n
    for i in numbers:
        for n in range(numbers.index(i)+1, len(numbers)):
            muldiv += ln/(i * numbers[n])

    for n in numbers:
        totdiv *= n

    answer = ln - (div - muldiv + ln/totdiv)
    print("answer is ", math.floor(answer))

现在我很确定我在第二个函数的某个地方搞砸了，因为它似乎对更多数字不起作用。例如，如果我试图找到

1到1000之间有多少个数不能被数字2、3、5、7整除？

第一个方法返回 228 和 foo(numbers = [2,3,5,7]) 返回 300... 我我很确定 228 是正确答案，因为多一个数字意味着有更少的因素而不是更多，但我哪里错了？有没有更好的方法来解决这个问题？

Answer 1

你不需要算法，简单的数学就足够了:

假设您要计算从 1 到 N(含)可被 k 整除的数字的数量，这简单地等同于:

楼层(N/k)。

因此在这种情况下可被 3 整除的数字的数量是 333。

但是，现在您不能简单地使用计算可被 2、3 和 5 整除的数字的数量；并总结它们，因为有共同点。事实上:例如 15 可以被 3 和 5 整除。

您可以使用 inclusion-exclusion principle 解决此问题:

能被2、3、5整除的数的个数是一样的

• 可被 2 整除的数量
• 加上能被 3 整除的数
• 加上能被5整除的数
• 减去可被 2 和 3 整除的数
• 减去可被 2 和 5 整除的数
• 减去可被 3 和 5 整除的数
• 加上可被 2、3 和 5 整除的数字的数量。

所以为了解决你的第一个问题，你可以简单地声明:

def n_div(N,k):
    return N//k

def n_div235(N):
    return n_div(N,2)+n_div(N,3)+n_div(N,5)-n_div(N,2*3)-n_div(N,2*5)-n_div(N,3*5)+n_div(N,2*3*5)

def not_div235(N):
    return N-n_div235(N)

如您所见，它生成了正确的结果:

>>> not_div235(1000)
266

只要 N 与除数的数量相比非常大，您最好使用包含 - 排除方法:

你可以这样做:

import itertools
from functools import reduce
import operator

def gcd(a, b):
    while b:      
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def lcm_list(ks):
    res = 1
    for k in ks:
        res = lcm(res,k)
    return res

def n_div_gen(N,ks):
    nk = len(ks)
    sum = 0
    factor = 1
    for i in range(1,nk+1):
        subsum = 0
        for comb in itertools.combinations(ks,i):
            subsum += n_div(N,lcm_list(comb))
        sum += factor * subsum
        factor = -factor
    return sum

def not_div_gen(N,ks):
    return N-n_div_gen(N,ks)

对于小的N，这不会得到返回，但是说要计算从1到1 000 000之间可被3、5和7整除的数字的数量000 是:

>>> not_div_gen(1000000000,[3,5,7])
457142857

你可以这样做:

>>> sum(i%3!=0 and i%5!=0 and i%7!=0 for i in range(1,1000000001))
457142857

但这需要几分钟才能计算出来，而我们自己的方法需要几毫秒。请注意，这仅适用于巨大的 N。