isMultiple的不必要调用：'''
If we list all the natural numbers below 10 that are multiples of 3 or 5,
we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
'''
end = 1000
def Solution01():
'''
Solved by brute force
#OPTIMIZE
'''
sum = 0
for i in range(3, end):
if isMultiple(i):
sum += i
print(sum)
def isMultiple(i):
return (i % 3 == 0) or (i % 5 == 0)
#1 楼
对于n = 333，总和3 + 6 + 9 + 12 + ... + 999 = 3（1 + 2 + 3 + ... + 333）= 3（n（n + 1））/ 2。 1000/3，其中“ /”是整数算术运算。此外，请注意15的倍数被计数两次。
So
def sum_factors_of_n_below_k(k, n):
m = (k-1) // n
return n * m * (m+1) // 2
def solution_01():
return (sum_factors_of_n_below_k(1000, 3) +
sum_factors_of_n_below_k(1000, 5) -
sum_factors_of_n_below_k(1000, 15))
评论
\ $ \ begingroup \ $
这显然是最有效的。我本打算将其发布为一体，但我更喜欢您将其分解的方式。仍然，sum_multiples_of_n_below_k是合适的名称吗？它们不是n的因数，而是其倍数
\ $ \ endgroup \ $
– jon_darkstar
2011年5月4日15:19
#2 楼
我认为消除可能的检查的最佳方法是这样的：valid = set([])
for i in range(3, end, 3):
valid.add(i)
for i in range(5, end, 5):
valid.add(i)
total = sum(valid)
仍然存在一些冗余（对3和5的倍数进行检查）两次），但这是最小的。
评论
\ $ \ begingroup \ $
@gddc：很好，我什至不知道您可以在这样的范围内指定增量。
\ $ \ endgroup \ $
– Robert S Ciaccio
2011年1月19日，21：25
\ $ \ begingroup \ $
那也是我现在要做的。
\ $ \ endgroup \ $
–罗勒
2011年1月19日21:26
\ $ \ begingroup \ $
@calavera-range（）是一个很棒的函数...作为第3个参数的可选步骤可以节省大量迭代次数。
\ $ \ endgroup \ $
– g.d.d.c
2011年1月19日21:26
\ $ \ begingroup \ $
docs.python.org/library/functions.html#range只是为了很好
\ $ \ endgroup \ $
– sova
2011年1月19日在22:03
\ $ \ begingroup \ $
另外，通过使用set.update方法，您可以摆脱循环并写一些东西：valid.update（xrange（3，end，3））
\ $ \ endgroup \ $
–鲨鱼先生
2011年1月27日19:38
#3 楼
我会摆脱for循环并在生成器表达式上使用sum。def solution_01(n):
partialsum = sum(xrange(3, n, 3))
return partialsum + sum(x for x in xrange(5, n, 5) if x % 3)
请注意，对于python 2，我们使用
xrange而不是range。我从未见过对于for循环或生成器表达式而言，这并不快。与sum循环中使用生成器表达式相比，使用for生成器表达式的速度也应该更快。如果要使用集合，则仍然不需要
for循环def solution_01(n):
values = set(range(3, n, 3)) | set(range(5, n, 5))
return sum(values)
这里，我们只是将倍数传递给set构造函数，将两个set的并集返回它们的和。在这里，我使用的是
range而不是xrange。出于某种原因，我已经知道传递给list时速度更快。我想Q4312079q也会更快。您可能会想要进行基准测试。#4 楼
好吧，这毕竟是对欧拉计画问题的答案，因此也许最好的解决方案基本上是铅笔纸。sum(i for i in range(n + 1)) # sums all numbers from zero to n
是一个三角数，与
n * (n + 1) / 2
这是我们都知道并喜欢的三角函数。更确切地说，是
triangle(n) = n * (n + 1) / 2
考虑到这一点，我们接下来注意到该系列的总和
3, 6, 9, 12, 15, 18, 21, 24, ...
是3 *上面的三角函数。而
5, 10, 15, 20, 25, 30, 35, ...
的和为5 *三角函数。但是，由于这些总和存在一个问题，因为在每个三角形数中都将计入一个像15或30的数字。不用担心，包含-排除原则可以解救！
15, 30, 45 ,60, 75, 90, 105, ...
的和为15 *三角函数。好吧，如果到目前为止没有什么意义，请不要担心。求出从1到n的级数之和，以k为增量，
triangle_with_increments(n, k = 1) = k * (n/k) * (n/k + 1) / 2
并用包含与排除原理，最后的答案是
triangle_with_increments(100, 5) + triangle_with_increments(100, 3) - triangle_with_increments(100, 15)
哇。谁打过？一个n复杂性问题突然变成一个固定时间的问题。那就是我所谓的优化恕我直言：P。但实际上，欧拉计划要求您以尽可能低的计算复杂度来回答问题。
#5 楼
我会这样：total = 0
for i in range(3, end, 3):
total += i
for i in range(5, end, 5):
if i % 3 != 0: # Only add the number if it hasn't already
total += i # been added as a multiple of 3
基本方法与gddc相同：迭代3的所有倍数，然后是5。但是，不使用集合要删除重复项，我们只需检查5的倍数是否也不是3的倍数。这样做有以下好处：
检查除数比添加到集合中要便宜。
我们以增量方式累加总数，因此不需要在末尾求和。
我们摆脱了集合，因此只需要恒定的空间。
评论
\ $ \ begingroup \ $
您认为允许添加重复的5并减去15会更快还是更慢？我们将失去end / 5可除性检查，并且只花费加法/ 15减法
\ $ \ endgroup \ $
– jon_darkstar
2011年5月4日15:24
#6 楼
g.d.d.c的解决方案有点多余，因为它会检查3和5的倍数的数字两次。我想知道对此的优化，所以它比注释稍长，但本身并不是真正的答案，因为它完全依靠gddc的出色答案作为灵感。如果添加倍数到多个“ 3”的有效列表，然后再对整个列表（1-1000）进行多个“ 5”传递，那么您确实会遇到一些冗余。
您的顺序添加它们：
add 3-multiples first
add 5 multiples second
如果要检查列表中是否存在该号码，将很重要（尽管有一点）。
是的，如果您的算法类似于
add 3-multiples to the list
add 5-multiples to the list if they don't collide
，它的性能会比
add 5-multiples to the list
add 3-multiples to the list if they don't collide
差一点，也就是说，因为3的倍数多于5的倍数，所以您要进行更多的“如果它们不发生冲突”的检查。
因此，在以下方面要记住一些想法：优化：
最好是一次遍历列表
如果我们没有检查不是3或5的倍数的数字，那么
一种可能的方法是注意倍数的频率。也就是说，请注意3和5的LCM（最小公倍数）为15：
3 6 9 12 15 18 21 24 27 30
|| ||
5 10 15 20 25 30
因此，在最佳情况下，您需要反复使用（1,15）范围内的3和5的倍数的频率表示，直到达到1000。（实际上是1005除以15均匀地乘以67次）。
您想要的，对于这种频率表示形式的每次迭代：
以下位置的数字：3 5 6 9 10 12 15
您的频率出现了（我是在构成声带为此，因此，如果起始索引从0k +1到67k（1到1005）[技术上为66k]，请更正我（如果有更好的数学y字）
您希望从索引中枚举位置3、5、6、9、10、12和15的数字。
因此，
for (freq_index = 0; freq_index < 66; ++freq_index) {
valid.add(15*freq_index + 3);
valid.add(15*freq_index + 5);
valid.add(15*freq_index + 6);
valid.add(15*freq_index + 9);
valid.add(15*freq_index + 10);
valid.add(15*freq_index + 12);
valid.add(15*freq_index + 15); //also the first term of the next indexed range
}
，我们消除了冗余
=）
<<以三个整数作为参数xyz，并且在没有冗余的情况下找到x和y的所有倍数，范围是1到z。
（基本上是我上面所做的概括）。
评论
\ $ \ begingroup \ $
我必须检查文档才能确定，但是我相信set.add（）方法使用二进制查找来确定新元素是否已经存在。如果这是正确的，那么检查3或5的倍数的顺序就无关紧要-您具有相同数量的二进制查找。如果您可以实施一种解决方案，从而避免对两者的倍数进行重复检查，那么您可能会有所改进。
\ $ \ endgroup \ $
– g.d.d.c
2011年1月19日在22:44
\ $ \ begingroup \ $
@ g.d.d.c：嗯，好点。由于最原始的实现方式无法高效地进行操作，因此我在语言上更加不确定。关于Google的python
.add（）函数的有趣补充：indefinitestudies.org/2009/03/11/dont-use-setadd-in-python
\ $ \ endgroup \ $
– sova
2011年1月20日，1：14
\ $ \ begingroup \ $
@sova-感谢您在工会操作员上的链接。我从来没有遇到过这种情况，通常我的设备足够小，不会受到性能损失的影响，但是知道替代方法总是很棒的。
\ $ \ endgroup \ $
– g.d.d.c
2011年1月20日下午16:46
\ $ \ begingroup \ $
@ g.d.d.c，上述解决方案的确排除了对两者的倍数的双重检查，它确定了可以重复数字模式的最小频率（最高为两位数字的LCM）。 3、5或两者的每个有效倍数仅被“检查”一次（实际上，不是真的被检查过，只是被添加了）。
\ $ \ endgroup \ $
– sova
2011年1月20日22:45
\ $ \ begingroup \ $
@ g.d.d.c python的设置基于哈希表。它不会使用二进制查找。相反，它将执行哈希表查找。
\ $ \ endgroup \ $
–温斯顿·埃韦特（Winston Ewert）
2011-02-24 17:57
#7 楼
也可以使用生成器：print sum(n for n in range(1000) if n % 3 == 0 or n % 5 == 0)
请注意，此处的意图并不十分清楚。对于共享代码，我希望使用类似
def euler001(limit):
return sum(n for n in range(limit) if n % 3 == 0 or n % 5 == 0)
print euler001(1000)
#8 楼
列表理解是一个很棒的解决方案，但是使用set的速度要快得多：from __future__ import print_function
def euler_001(limit):
s1, s2 = set(range(0, limit, 3)), set(range(0, limit, 5))
return sum(s1.union(s2))
print(euler_001(1000))
#9 楼
我使用了稍微简单一些的方法，但实际上做了同样的事情：total = 0
for n in range(3,1000):
if n % 3 == 0:
total += n
elif n % 5 == 0:
total += n
print total
elif确保只对任何因子/除数计数一次。评论
\ $ \ begingroup \ $
（同一件事：答案的显示顺序必定会发生变化，您可能是在问这个问题：请用引号或超链接消除歧义（例如，末尾的共享链接）每个帖子）。）
\ $ \ endgroup \ $
–灰胡子
16 Sep 4 '16 at 0:38
评论
您是要优化算法还是代码本身？@乔·菲利普斯：为什么不两者兼而有之？ ;）
@JoePhillips：算法。目前，它检查3到1000之间的每个整数。
@Zolomon：好点，任何一种答案都会有帮助。
请注意。如果您还不了解数学，那么对Wikipedia上的Richard's Answer的详细解释可能会有所帮助。见这里。