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

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都可以分割.

您可以使用包含 - 排除原则解决此问题:

可分为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,这不会得到回报,但是想要计算可分为3,5和7从1到1 000 000 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.

Answer 2

使用内置函数sum和all嵌套生成器：

def f(r=1000, nums=(2,3,5)):
    return sum(all(x%n for n in nums) for x in range(1, r+1))

这将遍历数字范围，检查每个数字是否与每个指定数字具有非零模数，并对这些布尔值（False是 0 和True是 1）求和。A numsof(2,3,5,7)产生的结果为 228，这与您的更短、更简单的代码一致（令人放心的是，它不像您的第二个代码块那样使用任何浮点算术）。