我试图在Project Euler上推广问题1的最佳答案，并意识到在使用包含/排除方法时，如果您输入的列表中的一个数字是列表中任何其他数字的倍数，则答案会出错。
例如，如果限制为1000，列表为[3，5，6，8]，则答案为306004，但答案应为266824。这是因为6是3的倍数，需要删除。
我想出了以下代码来从列表中删除多余的倍数：
def cleanMults(mults):
m = sorted(mults)
x = [m[0]]
for i in range(len(m) - 1, 0, -1):
multFound = False
for j in range(i - 1, -1, -1):
if m[i] % m[j] == 0:
multFound = True
break
if multFound == False: x.append(m[i])
return sorted(x)
在这里，我对列表进行排序(以防它无序(，然后从列表中的最后一个元素开始，将每个元素与其他元素进行比较。如果一个元素被另一个元素除，结果是余数为0，那么我们将multFound=True设置为break，并且不将其添加到解决方案列表中。否则，如果没有找到除数，我们会将其添加到列表中。
我的问题是，有没有更优化的方法来做到这一点？即使忽略排序，它也会在O(n^2(时间内运行。我知道有一种方法可以在O(n-log(n((时间内比较两个列表，但这与那不太一样。这里有人有什么想法或解决方案吗？
您可以使用gcd函数在列表中前后移动一次。这将允许您识别列表中至少有一个倍数的除数(例如3(。然后可以根据这些除数过滤列表。
from math import gcd
def cleanMult(A):
divisors = []
for d in (1,-1):
seen = 1
for a in A[::d]:
if seen%a: seen = a*seen//gcd(a,seen)
else: divisors.append(a)
return [a for a in A if all(d==a or a%d for d in divisors)]
print(cleanMult([3,5,6,8]))
# [3, 5, 8]
print(cleanMult([6,5,9,15,16,12,8]))
# [6, 5, 9, 8]
然而，对于欧拉问题一，有一种非常简单的方法可以得到答案：
sum(n for n in range(1,100) if n%5==0 or n%3==0)
你也可以生成所有倍数，并将它们放在一个集合中，每个只计数一次：
multiset = set()
N = 1000
for f in [3,5,6,8]:
multiset.update(range(f,N,f))
total = sum(multiset)
# 266824
或者从筛子或Eratosthenes:中获得一些灵感
N=1000
sieve = [0]*N
for f in [3,5,6,8]:
sieve[f::f] = range(f,N,f)
total = sum(sieve)
# 266824
至少，您需要收集所有数字，消除重复，排序，然后将较低的数字与较高的数字进行比较。您可以使用一些技巧来简化流程；您可以制作位图、检查素性等。但是，您仍然有一个固有的O(N^2(过程。
然而，解决原始问题的更快方法是取单个算术序列的和：
min3 = 3
max3 = (1000 // 3) * 3
cnt3 = max3 // 3
sum3 = (min3 + max3) * cnt3/ 2
min5 = 5
max5 = (1000 // 5) * 5
cnt5 = max5 // 5
sum5 = (min5 + max5) * cnt5 / 2
现在，由于您已经用和这两个因子对所有事物进行了双重计数，因此需要减去15的倍数的额外实例。以相同的方式计算sum15。
最后：
total = sum3 + sum5 - sum15
为了将其推广到更多的因子，必须将复数减去k-1次，其中k是因子的数量。将其推广到您的一般情况可能会，为您提供比删除倍数更省时的解决方案。
简言之，进行直接序列计算大大降低了具有额外因子的成本。
这能让你动起来吗？
以下是我目前拥有的：
import time
from math import prod
from itertools import combinations as co
def SoM(lim, mul):
n = (lim - 1) //mul
return (n * (n + 1) * mul) // 2
def inex(lim, mults):
ans = 0
for i in range(len(mults)):
for j in co(mults, i + 1):
ans += (-1)**i * SoM(lim, prod(list(j)))
return ans
def cleanMults(mults):
m = sorted(mults)
x = [m[0]]
for i in range(len(m) - 1, 0, -1):
multFound = False
for j in range(i - 1, -1, -1):
if m[i] % m[j] == 0: multFound = True
if multFound == False: x.append(m[i])
return sorted(x)
def toString(mults):
if len(mults) == 1: return str(list(mults)[0])
s = 'or ' + str(list(mults)[-1])
for i in range(len(mults) - 2, -1, -1):
s = str(list(mults)[i]) + ', ' + s
return s
def SumOfMults(lim, mults):
#Declare variables
start = time.time()
strnums, m = '', cleanMults(mults)
#Solve the problem
ans = str(inex(lim, m))
#Print the results
print('The sum of all of the multiples of ')
print(toString(mults) + ' below ' + str(lim) + ' is ' + ans + '.')
print('This took ' + str(time.time() - start) + ' seconds to calculate.')
我假设没有重复，但如果有，我所要做的就是将列表强制转换到一个集合，然后再次返回到列表。
你这么说：
"为了将其推广到更多的因子，必须将复数减去k-1次，其中k是因子的数量">
你能用例子更详细地说明你的意思吗？
在列表[3，5，26]这样的例子中，26是一个复合数，它只有2个因子(2和13(，所以如果我理解正确的话，26的所有因子的总和需要从总数中减去一次吗？
根据我的逻辑，我目前确实做了以下事情：
sum3+sum5+sum26-sum78(26*3(-sum130(26*5(-Sum 15(3*5(+sum1170(3*5*26(。
你是不是建议有一种更有效的方法来计算这个？