广义项目Euler 1：敲碎坚果的大锤

def sum_divisible_naive(divisors=[3, 5], start=0, stop=100):
    count = 0
    for num in xrange(start, stop):
        for d in divisors:
            if num % d == 0:
                count += num
                break
    return count

def divisible_by_k(k, start=0, limit=100):
    stop = int((limit-1)/float(k))
    return k*(stop+start)*(stop-start+1)/2

total = divisible_by_k(3) + divisible_by_k(5)

total = divisible_by_k(a) + divisible_by_k(b) - sum_divisible_by_k(a*b/gcd(a, b))

def remove_multiples(divisors):
    i = 0
    divisors = sorted(set(divisors))
    divisors_len = len(divisors)
    while i < divisors_len:
        j = i + 1
        while j < divisors_len:
            if divisors[j] % divisors[i] == 0:
                divisors.remove(divisors[j])
                divisors_len -= 1
            else:
                j += 1
        i += 1
    return divisors

#1 楼

背景

让\ $ N \ $为范围的大小[开始，停止）。 \ $ N = \ textrm {停止}-\ textrm {开始} \ $。

让\ $ M \ $为除数列表的大小。 \ $ M \ $ = \ $ \ lvert \ textrm {除数} \ rvert \ $

天真的方法是\ $ \ Omega（N）\ $，而您的方法是\ $ \ mathcal {O }（2 ^ M）\ $，因为您必须迭代除数列表的幂集。

变量命名

我知道k只是一个通用的迭代器名称，但以下代码令我感到困惑：

total += k*sum_divisible_by_k(product, start, stop)

为符号转换迭代器使用其他通用名称，例如j，s或k以外的其他名称。 br />
错误

在sum_divisible_by_k中直接使用start是不正确的。相反，您应该计算\ $ \ lceil \ frac {start} {k} \ rceil \ $。另外，对于stop，您可以只使用整数除法\ $ \ lfloor \ frac {limit-1} {k} \ rfloor \ $。

反模式

迭代在我知道的大多数语言中，删除值时使用列表是一种反模式。如此处另一个答案所述，我建议您建立一个新列表。

记忆化

您先前计算出的gcd的dict在两个方面都不理想。


您只存储gcd的先前值，因此仍然需要对每个除数组合执行乘法。例如，在除数集中\ $ \ {a，b，c，d，e \} \ $中，您将计算\ $ a \ cdot b \ textrm {，} a \ cdot b \ cdot c \ textrm {，} a \ cdot b \ cdot c \ cdot d \ textrm {，} a \ cdot b \ cdot c \ cdot d \ cdot e \ $。您应该存储实际的lcm，而不仅仅是存储gcd的中间步骤。

\ $ \ textrm {lcm}（a，b，c）= \ textrm {lcm}（\ textrm {lcm}（a，b），c）\ $我相信您知道。但是，在计算\ $ \ textrm {lcm}（a，b，c，d，e）\ $时，您正在执行\ $ \ textrm {lcm}（a，b）\ $的查找，然后是\ $ \ textrm {lcm}（\ textrm {lcm}（a，b），c）\ $然后是\ $ \ textrm {lcm}（\ textrm {lcm}（\ textrm {lcm}（a，b），c）， d）\ $，等等。您可以执行\ $ 1 \ $查找，而不是对长度为\ $ L \ $的列表的lcm执行\ $ L-1 \ $查找。

从itertools ：


组合以字典顺序排序。因此，如果对输入iterable进行了排序，则将按排序顺序生成组合元组。


假设您首先从最小的组合开始（当前是），则可以确保当前已删除最后一个元素的组合已在dict中。也就是说，确定\ $ \ textrm {lcm}（a，b，c，d）\ $时，我们总是可以从dict中获取\ $ \ textrm {lcm}（a，b，c）\ $。 />

组合逻辑

为了方便起见，通常将数学值赋予某些表达式。例如，\ $ 0！= 1 \ $。为您提供一个方便的值是定义\ $ \ textrm {lcm}（\ textrm {（）））= 1 \ $，以便\ $ \ textrm {lcm}（\ textrm {（）}，a）= a \ $。然后，您可以将sum_divisors_fast中的两个外部循环合并为一个循环。

更新代码

原始版本

from itertools import combinations
from fractions import gcd

lcm_dict = {():1}

def lcm(a, b):
    return a * b // gcd(a, b)

def lcm_list(perm):
    l = lcm(lcm_dict[perm[:-1]], perm[-1])
    lcm_dict[perm] = l
    return l

def remove_multiples(divisors):
    # Directly from Joe Wallis's answer
    new_divisors = []
    divisors = sorted(set(divisors))
    for divisor in divisors:
        if not any(divisor % d == 0 for d in new_divisors):
            new_divisors.append(divisor)
    return new_divisors

def ceil_div(a, b):
    return -(-a // b)

def summation_from_zero(n):
    return n * (n+1) // 2

def sum_divisible_by_k(k, start, stop):
    sum_start = ceil_div(start, k)
    sum_stop = (stop - 1) // k
    return k * (summation_from_zero(sum_stop) - summation_from_zero(sum_start-1))

def sum_divisible_fast(div=[3,5], start=0, stop=100):
    divisors = remove_multiples(div)    
    total = 0

    j = 1
    for i in xrange(1, len(divisors)+1):
        for perm in combinations(divisors, i):
            product = lcm_list(perm)
            total += j * sum_divisible_by_k(product, start, stop)
        j = -j

    return total


def sum_divisible_naive(divisors=[3, 5], start=0, stop=100):
    count = 0
    for num in xrange(start, stop):
        for d in divisors:
            if num % d == 0:
                count += num
                break
    return count


if __name__ == '__main__':

    list_to_test = [2, 6, 9, 8]
    start = 2
    stop = 10**5
    print sum_divisible_naive(list_to_test, start, stop)
    print sum_divisible_fast(list_to_test, start, stop)


    print sum_divisible_naive()
    print sum_divisible_fast()

更新

timeit.timeit('orig.sum_divisible_naive([3,5,7,11,13,17,19,23,29,31,37,39,41], 0, 10**7)', 'from __main__ import orig', number=1)
5.059425115585327
timeit.timeit('orig.sum_divisible_fast([3,5,7,11,13,17,19,23,29,31,37,39,41], 0, 10**7)', 'from __main__ import orig', number=10)
0.2042551040649414
timeit.timeit('orig.sum_divisible_fast([3,5,7,11,13,17,19,23,29,31,37,39,41], 0, 10**7)', 'from __main__ import orig', number=100)
1.8143179416656494

/>

#2 楼

您的数学比我的数学好得多，因此我无法对此发表评论。

但是，如果您以其他方式遇到问题，可以简化您的函数remove_multiples。
通常与从旧列表中删除相比，将其添加到新列表中更容易。

这种方法的工作方式不是检查您添加的数字之后的所有数字是否都正确，而是检查是否可以通过查看前面的数字来确定数字。
那么您可以实现一个简单的功能：

说任何sorted(set(divisors))小于任何new_divisors。
除非您将负数传递给它。
由此我们可以遍历divisors，如果它可以被任何divisor整除，则将其删除。 。

#3 楼

gcd_dict / gcd_list的东西可能更具表现力。

例如，由于您要使用备忘录，因此可以明确地说出来。可以完成这项工作的简单装饰器将比您的gcd_list占用更少的空间，并且可以重复使用。

看看这一点-当然，这对于一项任务来说是过大的，但是您会发现一些用处如果您以后继续执行Euler项目任务，则可以记住装饰者，因此将时间花在一个好的人身上会有所作为。


remove_multiples已经被另一个海报覆盖。我要补充一点，可以使用一些巧妙的reduce而不是迭代来缩短它，但是我不能说肯定会有所改进。


您有2条代码会增加/用total减少sum_divisible_by_k。当然，让读者理解第一部分的内容会更简单，但是无论如何，读者都必须理解第二部分。因此，可以将range(2, len(divisors)+1)替换为range(1, len(divisors)+1)，并将初始k值设置为1-然后可以完全摆脱for divisor in divisors:循环。

此外，k的含义也不明显。如果对偶数大小的排列表示“ -1，对于奇数大小的排列表示1”，则应这样说。例如1 if (len(perm) % 2) else -1。不用担心，len()很快。

如果您找不到product可以吸引眼球，则可以将reduce移到一个单独的功能上，但这只是个人喜好。 >

#4 楼

我认为还有一个额外的速度。令N为停止-开始，k为除数。考虑k << << N，例如除数= {3,5}，开始= 1，停止= 1百万的情况。

我们不需要执行\ $ O（N）\ $查找，我们可以在\ $ O（1）\ $中计算3的倍数之和。它是3 *（1 + 2 + 3 + 4 ... floor（1 Million / 3）），减少为众所周知的3 * n（n-1）/ 2个公式。

现在您的问题只需要\ $ O（k ^ 2）\ $而不是\ $ O（N）\ $，这可能要快得多。