Project Euler-Multiples of 3 and 5-Problem 1

2018/01/25 18:02

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.

分析

3 的倍数可以表示为 n%3 == 0
5 的倍数可以标识为 n%5 == 0

method 1



def sumN(n):

    return sum[i for i in range(1,n) if i%3 == 0 or i%5 == 0]



method 2

3 的倍数:3,6,9....,n//3

5 的倍数:5,10,15,....,n//5



def method3(n):

    sum_3 = sum([i for i in range(1,n,3)])

    sum_5 = sum([i for i in range(1,n,5)])

    sum_15 = sum([i for i in range(1,n,15)])

    return (sum_3 + sum_5 - sum_15)



method 2 的优化

3,5,6,9,10,12,15,18,20,21,24,25,27,30,33,35,40... 好像没看出什么,我们尝试把 3 的倍数全部移除

5,10,20,25,35,40 现在是不是看出来什么了?还没看出什么?再看

5,20,35... 和 10,25,40... 全新的两个序列



def method3_promote(n):

    sum_3 = sum([i for i in range(1,n,3)])

    sum_5 = sum([i for i in range(1,n,15)])

    sum_10 = sum([i for i in range(1,n,15)])

    return (sum_3+sum_5+sum_10) 



method 3

3 的倍数: 3,6,9,...,n

5 的倍数: 5,10,15,...,n

15 的倍数: 15,30,45,...,n



def SumDivisibleBy(n,target=999):

    p = target // n       # a1 = n, an = p*n

    return n*(p*(p+1))/2  # (a1+an)xp/2 

SumDivisibleBy(3)+SumDivisibleBy(5)-SumDivisibleBy(15)



0
0 收藏

0 评论
0 收藏
0