从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 / 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//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,7]) 457142857
你可以这样做：
>>> sum(i%3!=0 and i%5!=0 and i%7!=0 for i in range(1,1000000001)) 457142857
但是计算它需要几分钟,而我们自己的方法使用毫秒.请注意,这仅适用于巨大的N.