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

概述所以我遇到了这个问题： 从1到1000有多少个数字不能被数字2,3和5整除？ 起初看起来很简单,所以我写了一个快速的python程序来解决它： count = 0for number in range(1,1000): if number % 2 != 0 and number % 3 != 0 and number % 5 != 0: count += 1print( 所以我遇到了这个问题：

从1到1000有多少个数字不能被数字2,3和5整除？

起初看起来很简单,所以我写了一个快速的python程序来解决它：

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

我得到了正确的答案(266),但我认为如果我想检查的不仅仅是3个值,那么这样做是很多打字.我也想做一个数学解决方案所以我遇到了这个：

1000 – ((1000/2 1000/3 1000/5) – (1000 / 2×3 1000 / 2×5 1000 / 3×5)(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,5和7整除？

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

解决方法 你不需要算法,简单的数学就足够了：

假设你想要计算从1到N(包括)的数字量,可以用k分割,这相当于：

地板(N / K).

因此,在这种情况下可分为3的数字是333.

然而,现在你不能简单地使用计算可分为2,3和5的数字的数量;并总结,因为有共同点.确实：例如,15和3都可以分割.

您可以使用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//kdef 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 itertoolsfrom functools import reduceimport operatordef gcd(a,b):    while b:              a,b = b,a % b    return adef lcm(a,b):    return a * b // gcd(a,b)def lcm_List(ks):    res = 1    for k in ks:        res = lcm(res,k)    return resdef 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 sumdef 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,7])457142857

你可以这样做：

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

但是计算它需要几分钟,而我们自己的方法使用毫秒.请注意,这仅适用于巨大的N.

总结

以上是内存溢出为你收集整理的python – 解决这个难题的最佳算法是什么？全部内容，希望文章能够帮你解决python – 解决这个难题的最佳算法是什么？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。