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

所以我遇到了这个问题：

从 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是正确的答案，因为多一个数字意味着因素更少而不是更多，但我哪里出错了？有没有更好的方法来解决这个问题？

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

假设你想计算从 1 到N(含)除以k的数字数量，这简直等价于：

地板(不适用)。

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

然而，现在你不能简单地计算可除以2,3和5的数字数量;并将它们相加，因为有共同的数字。事实上：例如 15 可以除以 3 和 5。

但是，您可以使用包含-排除原则来解决此问题：

可除以 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 000 的可除以 3、5 和 7 的数字数量是：

>>> 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。

将内置函数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)。nums(2,3,5,7)产生的结果为 228，这与更短、更简单的代码一致(令人放心的是，它不像第二个代码块那样使用任何浮点算法)。

不能被 n_1，n₂,...,n_t整除的整数数(假设为成对互质数)为

最多 N 减去的整数数( 1..t 中的 SUM i(最多 N 的整数数可被 n i 整除))加上 ( 1..t 中的 SUM i，j，iin_jn_{k n}_l整除))减去... ...
... ...
( 总和_{i，j，k，l,...Q in 1..t， i<...>}(最多 N 的整数数可被 n_in_jn_{k n}_l整除...n_q))

序列将继续，直到下标包含原始列表中的所有t整数。

对于未知为成对互质数的数字，将其乘积替换为最小公倍数。

这就是为什么您的方法仅适用于 3 个数字的原因。您只计算序列的前四个成员。

这是另一个使用包含-排除的实现。它比 Willem Van Onsem 的出色答案中的代码更简单(我在编写此代码之前没有看到)，但这个只有在除数列表中的数字都相互互质时才有效。对于更一般的情况，您需要使用 William 的方法。

from itertools import combinations
from functools import reduce
def prod(seq, mul=int.__mul__):
return reduce(mul, seq, 1)
def count_coprimes(n, divisors):
total = n
sign = -1
for i in range(1, len(divisors) + 1):
for k in combinations(divisors, i):
total += n // prod(k) * sign
sign = -sign
return total
print(count_coprimes(1000, [2, 3, 5]))

输出

FWIW，这是与"单行"相同的算法(分为几行以提高可读性)。由于内部循环中的(-1)**i，效率会降低一些。

def count_coprimes(n, divisors):
return n + sum(n // prod(k) * (-1)**i
for i in range(1, len(divisors) + 1)
for k in combinations(divisors, i))
print(count_coprimes(1000000000, [3, 5, 7]))

输出

457142857

我们可以通过取反除数并使用修改后的整数除法函数来摆脱该(-1)**i：

def div(p, q):
return p // q if q > 0 else -(p // -q)
def count_coprimes(n, divisors):
return sum(div(n, prod(k))
for i in range(len(divisors) + 1)
for k in combinations([-u for u in divisors], i))

您可以进行的一个非常小的更改是生成从 1 到 1000 的所有数字，而不是生成从 1 到 1000 的所有数字：

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

虽然这不是一个巨大的变化，也不是一个数学解决方案，但它使代码的可读性不低，效率略高。

为了考虑你的其他代码，你可以在 if 语句中使用列表推导来检查其他数字(请注意，我也使用第一个数字来生成初始数字列表，而不是对所有 1000 个数字执行模运算)：

def foo(lst):
count = 0
for number in range(1,1001,lst[0]):
if not any([number % i == 0 for i in lst[1:]]):
count += 1
return count
>>> foo([2,3,5])
266
>>> foo([2,3,5,7])
228

有很多方法可以迭代解决这个小问题，它们的性能都非常相似，这里有几个例子：

import timeit

def f1(l, h):
count = 0
for number in range(l, h):
if number % 2 != 0 and number % 3 != 0 and number % 5 != 0:
count += 1
return count

def f2(l, h):
return len(filter(lambda x: x % 2 != 0 and x % 3 != 0 and x % 5 != 0, range(l, h)))

def f3(l, h):
count = 0
for number in range(l, h):
if number % 2 == 0:
continue
if number % 3 == 0:
continue
if number % 5 == 0:
continue
count += 1
return count

def f4(l, h):
return len([x for x in range(l, h) if x % 2 != 0 and x % 3 != 0 and x % 5 != 0])
a, b, N = 1, 1000, 10000
print timeit.timeit('f1(a,b)', setup='from __main__ import f1, a, b', number=N)
print timeit.timeit('f2(a,b)', setup='from __main__ import f2, a, b', number=N)
print timeit.timeit('f3(a,b)', setup='from __main__ import f3, a, b', number=N)
print timeit.timeit('f4(a,b)', setup='from __main__ import f4, a, b', number=N)

i7-2.6GHz 上的时间将是：

0.802361558825
1.46568073638
0.91737188946
0.846404330893

通常，当下限/上限(1,1000)相对较小时，可以考虑这些时间。现在，如果我们谈论的是计算不可行的非常高的界限(万亿)，您可以考虑应用更智能的包含-排除原则，这样您就可以通过分析解决问题，并允许您获得恒定的时间与解决方案。

输入

设n是测试<0,n>区间，d[]={2,3,5,0};为空终止的除数数组
计算d[]的 LCM

最小公倍数是SoE将重复的时间段。因为2,3,5是lcm=30.使用max(d[])作为增量，同时计算它以提高速度......如果LCM太大(LCM>=n)，则使用n代替速度。
计算适用于<0,LCM)的 SoE

只需创建LCM编号数组并为不可分割i设置a[i]=1，为可分割i设置a[i]=0。
将 SoE 转换为不可分割的数字计数

轻松计算a'[i]=a[0]+a[1]+..a[i]
计算计数

计数很简单：
```
int(n/LCM)*a'[LCM-1] + a'[n%LCM];
```

这里有一个简单的C++例子：

int non_divisibles(int n,const int *d)  // SoE
{
int i,j,cnt,lcm,m,*a;
for (m=0;d[m];m++); // compute m
for (cnt=0,i=0;i<m;i++) if (cnt<d[i]) cnt=d[i]; // cnt = max d[] (to speed up LCM)
// LCM d[]
a=new int[m]; if (a==NULL) return -1;
for (i=0;i<m;i++) a[i]=d[i];
for (lcm=cnt;lcm<=n;lcm+=cnt) // no need to test above `n` even if lcm is bigger
{
for (i=0;i<m;i++) for (;a[i]<lcm;) a[i]+=d[i];
for (i=0;i<m;i++) if (a[i]!=lcm) { i=-1; break; }
if (i>=0) break;
}
delete[] a;
// SoE <0,LCM)
a=new int[lcm]; if (a==NULL) return -1;
for (i=0;i<lcm;i++) a[i]=1;
for (j=0;d[j];j++)
for (i=0;i<lcm;i+=d[j])
a[i]=0;
// convert to cnt
for (i=1;i<lcm;i++) a[i]+=a[i-1];
// compute whole count
cnt =(n/lcm)*a[lcm-1];
cnt+=a[n%lcm];
delete[] a;
return cnt;
}

这里有一些测量来比较朴素，SoE和这个SoE(max(n，LCM(d[])))方法：

n=1000000 d[]={ 2 3 5 7 11 13 17 19 }
171021 [  27.514 ms] naive
171021 [  12.642 ms] SoE
171021 [  25.438 ms] LCM+Soe
n=1000000 d[]={ 2 3 5 7 11 13 17 }
180524 [  26.212 ms] naive
180524 [  11.781 ms] SoE
180524 [   9.807 ms] LCM+Soe
n=1000000 d[]={ 2 3 5 7 11 13 }
191808 [  24.690 ms] naive
191808 [  11.512 ms] SoE
191808 [   0.702 ms] LCM+Soe
n=1000000 d[]={ 2 3 5 }
266666 [  16.468 ms] naive
266666 [   9.744 ms] SoE
266666 [   0.006 ms] LCM+Soe
n= 1000 d[]={ 2 3 5 }
266 [   0.012 ms] naive
266 [   0.012 ms] SoE
266 [   0.001 ms] LCM+Soe
n=1000000 d[]={ 2 3 5 19 23 61 87 10001 }
237662 [  26.493 ms] naive
237662 [  10.180 ms] SoE
237662 [  19.429 ms] LCM+Soe

如您所见，如果LCM与n相比太大(d[]包含许多素数或大数字)，但需要O(n)空间，则SoE(n)更好。

一旦你击中可分割的，你就可以纾困。

def test(tocheck):
count = 0
for number in range(1, 1000):
for div in tocheck:
if not number % div:
break
else:
#else on a loop means it ran to completion w.o. break
count += 1
print("%d not divisible by %s" % (count, tocheck))

test([2,3,5])
test([2,3,5,7])

输出：

266 not divisible by [2, 3, 5]
228 not divisible by [2, 3, 5, 7]

def not_divisible(n = 1000, divisors = [2, 3, 5]):
count = 0
for i in range(1, n + 1):
if all(1 if i % d else 0 for d in divisors):
count += 1
return count

第四行解释：

如果数字 i 不能被除数 d 整除，则 i % d 返回非零整数。Python 认为任何非零数都是 True。
列表推导 [1 如果 i % d 否则 0 对于除数中的 d] 返回 a
1 和 0 的列表，这样，如果数字不可整除，则值为 1 ，否则 0.
all() 函数检查集合中的所有值是否为 True。如果列表中的所有值均为 1(True)，这意味着该数字被所有除数"not
整除"。
如果数字不能被 2 和 3 整除，则不能被 6.所以没有必要在这里检查。

下面是一个较小的代码：

def not_divisible(n = 1000, divisors = [2, 3, 5]):
return sum(1 for i in range(1, n + 1) if all(1 if i % d else 0 for d in divisors))

在这里，我们为不能被所有除数整除的每个数字生成一个 1 列表，该列表的总和就是答案。

相关内容

最新更新

热门标签：