求1000以内所有能够被3或者5整除的自然数的和

如果我们列出10以下所有能够被3或者5整除的自然数，那么我们得到的是3，5，6和9。这四个数的和是23。
那么请计算1000以下（不包括1000）的所有能够被3或者5整除的自然数的和。

---

看到这个问题，我们很自然地想到能够被3或者5整除的数，那么就是对3或5求余等于0的数嘛。然后依次地将这些数加在一起。就得到了所要的结果。那让我们试一下这种方法。

#coding=utf-8
from datetime import datetime
def Divisible(num, divider):
    return num % divider == 0
LIMIT = 1000
sum = 0
t_start = datetime.now()
for i in xrange(LIMIT):
    if Divisible(i, 3) or Divisible(i, 5):
        sum += i
t_end = datetime.now()
time_delta = t_end - t_start
#计算程序运行时间
last_seconds = time_delta.seconds + (time_delta.microseconds) / 100000.0
print(sum)
print(last_seconds)

运行一下得出结果如下：

233168
0.0

好像也没有花多久时间啊，那么我们把LIMIT值放大到1000, 000，10, 000, 000, 100, 000, 000再看看时间，本机的测试数据分别为4.33s，7.79s和52.04s。每个人的机器性能不同，可能得出的数据不太一样，但是有一点是肯定的，随着运算数据量的增加，机器耗时也随之飙升。现在我们想一想上面的算法的时间复杂度是O(n)。那么有没有好一点的方法呢？

我们想一想，对于1000以内能够被3或者5整除的数存在三类情况，第一个是只能被3整除，第二个是只能被5整除，第三个是能够同时被3和5整除（也就是能够被15整除）。我们可以将所有能够被3整除的自然数先累加，然后再将能够被5整除的自然数累加，最后减去同时被3和5整除的自然数的累加，最终得到结果。

$$\sum_{i=1}^m (a_i \% 3 == 0)+ \sum_{j=1}^n (b_j \% 5 == 0) - \sum_{k=1}^p (c_k \% 15 == 0)$$ 其中$a_i$, $b_j$, $c_k$分别为能够被3，5，15整除的1000以内的自然数。
现在等等，我们刚刚说到时间复杂度，那么这个方法如果仍然使用遍历累加的话，不是一样耗费时间么？
对的，那让我们想一想有没有什么其他的办法？
看到上面的公式了么，这个是数学题啊，从数学的角度思考，那些$a_i$不就是3，6，9，... , 999么，$b_j$不就是5，10，15，...，995么？这些是数列不是么，数列有数列公式不是么？先看看$a_i$，对于它来说，我们可以得到下面的数列公式$\sum_{}a_i=3*(1+2+3+...+m)$，变型一下就是$\sum_{}a_i=3*\frac{m(m+1)}{2}$，同样对于5和15我们也可以归纳出这样的公式。现在的问题就是如何确定这些m，n，p的值呢？想一想这些值是什么，这些值就是1000以内的能够分别整除这些3，5，15的最大自然数对3，5，15的商。是吧？既然这样我们就可以使用下面的方法。

#coding=utf-8
from datetime import datetime
def get_max_index(num, divider):
    max_index = num / divider
    if num % divider == 0:
        max_index -= 1
    return max_index
def get_sum_of_divisible(max_index, divider):
    return max_index * (max_index + 1) * divider / 2
LIMIT = 1000
sum = 0
t_start = datetime.now()
m = get_max_index(LIMIT, 3)
n = get_max_index(LIMIT, 5)
p = get_max_index(LIMIT, 15)
sum += get_sum_of_divisible(m, 3)
sum += get_sum_of_divisible(n, 5)
sum -= get_sum_of_divisible(p, 15)
t_end = datetime.now()
time_delta = t_end - t_start
#计算程序运行时间
last_seconds = time_delta.seconds + (time_delta.microseconds) / 100000.0
print(sum)
print(last_seconds)

嘿嘿，几乎不花什么时间吧！

好了，现在问题解决了，下面再额外想一个问题，对于我们第一种算法有没有办法提高它的运算效率呢？答案当然是有的。看看我们现在的电脑配置，各种双核，四核，内存8G, 16G的，想到什么了，并行编程！还记得我们刚刚说的么？对这个问题进行分解，得到的是我们可以分别计算能够整除3或者整除5的那些自然数的累加值，然后减去能够同时整除3和5（即能够整除15）的自然数的累加值。我们我们可以让这三个步骤并行执行，是不是会快一点呢？
我们采用目前支持并行编程的语言的Go语言来做例子:

package main
import (
    "fmt"
    "time"
)
func get_sum_of_divisible(num int, divider int, resultChan chan int) {
    sum := 0
    for value := 0; value < num; value++ {
        if value % divider == 0 {
            sum += value
        }
    }
    resultChan <- sum
}
func main() {
    LIMIT := 1000
    resultChan := make(chan int, 3)
    t_start := time.Now()
    go get_sum_of_divisible(LIMIT, 3, resultChan)
    go get_sum_of_divisible(LIMIT, 5, resultChan)
    go get_sum_of_divisible(LIMIT, 15, resultChan)
    sum3, sum5, sum15 := <-resultChan, <-resultChan, <-resultChan
    sum := sum3 + sum5 - sum15
    t_end := time.Now()
    fmt.Println(sum)
    fmt.Println(t_end.Sub(t_start))
}

我们直接把LIMIT改为100, 000, 000来看一下结果

3.5522032s

哇噢！酷！ :-P

顺便说一下机器配置：
1. CPU i7-2720AM
2. 主频 2.20GHz
3. 内存 8G
4. 操作系统 Windows7 企业版 64位

:-)