前言：

说真的不是很想写文章，因为总感觉写文章的时间可以写不少的代码。从这点触发，对个人来说，真的不是那么美好的想法，但是有道是好记性不如烂笔头，为了防止以后忘记，方便复习，特地的注册了一个账号，写下文章，不定期写点重要内容。由于个人最近在学习Python 3,所以代码都会用Python 3进行展示。如果有所欠缺的地方，估计是熟悉程度的问题。至于基于语言上的优化可能会比较差。毕竟刚刚学不久。。

本系列的全部题目在Euler上的数学题目，虽然题目很简单，也很容易实现，但是却发现有不少的乐趣在其中，本人怀着个人提升和分享的目的，将各种的解题思路给予大家一起探讨，有的思路从网上开始学习。可能表达不太如意，但会贴出连接的 ：D

---

Euler 第一题： Multiples of 3 and 5(3和5的倍数和)

题目描述：求一个数的3的倍数和5的倍数总和。例子：10的3的倍数是3,6,9;5的倍数是5;总和是23

1. 题目分析： 题目很简单，基本就是一个遍历的过程。刚开始的思路，就是为了解答，根本没想过优化啊，时间啊，空间啊，这种问题。于是就瞎写一段很简单的代码。

def func1(n):
  result = 0
  for i in range(n):
  if i % 3 == 0 or i % 5 == 0:
    result += i
return result

emm........结果很正确。除此之外，这段代码的确是有点简单过头了，就心想大名鼎鼎的Euler就这么简单，于是乎就找度娘，这道题的答案，别想从Euler上找你的答案，因为不知道为啥总感觉看起来特别费力。而且里面差劲的答案也是很多，点进去看答案，和我答案一样千篇一律，就不能给个最优解么？不过想了想这东西还真没有最优解，只有更优解。皇天不负有心人啊（其实没多难），终于在CSDN上找到一个也是写Euler的文章。戳我

相比本人写的的确好多了。。不过嘛，我也就是记录个人成长过程嘛。从这博客开始，才开始明白自己的代码的确是最差的。

既然是最差的，那么就有很大的优化空间。第一从遍历的过程来看，没有必要遍历每一个数字，也就是说在原有的思路上进行优化的过程：

def func1_2(n):
    result = 0
    for i in range(3, n, 3):
        result += i
    for i in range(5, n, 5):
        result += i
    return result

emmm....然而这里有个问题。就是会有重复数，也就是说每当是3并且5的倍数时，那么就会导致这个数多加了一次。需要过滤一下，过滤方案有2个，一个就是减去3 和 5的倍数和，第二个就是在第二次遍历禁止过多的3倍数加进来 或者 是在第一次遍历时去掉过多的5的倍数
那么方案一：

def func1_2_1(n):
    result = 0
    for i in range(3, n, 3):
        result += i
    for i in range(5, n, 5):
        result += i
    for i in range(15, n, 15):
        result -= i
    return result

方案二：

def func1_2_2(n):
    result = 0
    for i in range(3, n, 3):
        # if i % 5 == 0:
        #     continue
        result += i
    for i in range(5, n, 5):
        if i % 3 == 0:
            continue
        result += i
    return result

减少了遍历次数，但是如果我的数字很大呢？那么遍历还是不是一个比较好的方式？或者说不用遍历能不能实现？
如果将方案一种的每次遍历，单独取出来，在Python 3的语法中，也比较能够清晰的看到：每个循环的值就是以3、5、15开始的等差数列，熟悉不熟悉？那么根据等差数列的公式

sum = (a0+an)*n/2，n>=1

那么我们就可以那刚才的func1_2_1(n)函数进行修改，将所有遍历过程去掉，该用公式求解。^_

def func3(x):
    return arraysum(x, 3) + arraysum(x, 5) - arraysum(x, 15)

def arraysum(x, n):
    i = x // n  # //代表整除
    return n * (1 + i) * i / 2

用这样的方法可以去掉遍历的过程，减少了循环时间。
到此算是完成一个题目的求解，思考，改进的过程。

本文也许写的不是很好，但是其中的过程却是本人在求解时一步步被开导出来的。特此留下纪念！~

最终代码：

def func1(n):
    '''单纯通过循环遍历n的值，判断是不是3或者5的倍数，然后相加，时间和空间复杂度与n相关，O(n)'''
    result = 0
    for i in range(n):
        if i % 3 == 0 or i % 5 == 0:
            result += i
    return result

def func1_2_1(n):
    '''第二种方式，先获取所有的3和5的数，然后相加再减去重复值
    二次优化，减少遍历的次数，就是说将数据每次步数为3,5,15用以降低数据遍历次数 O(n) = O(n/3)+O(n/5)+O(n/15)'''
    result = 0
    for i in range(3, n, 3):
        result += i
    for i in range(5, n, 5):
        result += i
    for i in range(15, n, 15):
        result -= i
    return result

def func1_2_2(n):
    '''第二种方式，先获取所有的3和5的数，在遍历时过滤多余的3的倍数
二次优化，减少遍历的次数，就是说将数据每次步数为3,5,15用以降低数据遍历次数 O(n) = O(n/3)+O(n/5)'''
    result = 0
    for i in range(3, n, 3 or 5):
        # if i % 5 == 0:
        #     continue
        result += i
    for i in range(5, n, 5):
        if i % 3 == 0:
            continue
        result += i
    return result

def func3(x):
    '''和方式二有相似先计算3,5的项的总值然后在减去相同项
但是计算总值时使用等差数列公式计算，减少计算复杂度'''
    return arraysum(x, 3) + arraysum(x, 5) - arraysum(x, 15)

def arraysum(x, n):
    i = x // n
    return n * (1 + i) * i / 2

if __name__ == '__main__':
    print(func1.__doc__)
    time_start = datetime.datetime.now().microsecond
    print(func1(100000))
    time_end = datetime.datetime.now().microsecond
    print("time1 is {}".format(time_end - time_start))
    print(func1_2_1.__doc__)
    time_start = datetime.datetime.now().microsecond
    print(func2(100000))
    time_end = datetime.datetime.now().microsecond
    print("time1_2_1 is {}".format(time_end - time_start))
    print(func1_2_2.__doc__)
    time_start = datetime.datetime.now().microsecond
    print(func1_2_2(100000))
    time_end = datetime.datetime.now().microsecond
    print("time1_2_2 is {}".format(time_end - time_start))
    time_start = datetime.datetime.now().microsecond
    print(func3.__doc__)
    print(func3(100000))
    time_end = datetime.datetime.now().microsecond
    print("time3 is {}".format(time_end - time_start))

最终结果

欢迎大家有什么特别的解题思路大家一起探讨！~_!（^o^）!