[Project Euler]Problem 1

前段时间大家的推荐找到了 Peoject Euler 这个联系算法的网站，很有收获，和大家分享一下做题的经验。

Problem 1:

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或5的倍数的小于10的自然数，我们得到了 3 ,5,6 以及 9.这些数的和为 23.

找出小于1000的3或5的倍数的和。

方法一:

直接根据题意写代码:

def f1(n):
    return sum(i for i in range(n) if i%3==0 or i%5==0)

方法二:

3或5的倍数的和=3的倍数的和+5的倍数的和-15的倍数的和

因为15的倍数既是3的倍数又是5的倍数，被加了两次。

小于n的k的倍数为  k,2*k,3*k,……r*k,  r=floor((n-1)/k)

求和 得 (r*(r+1)*k)/2

View Code

def f2(n):
    Sum=lambda x:(x*x+x)//2
    SumDivisibleBy=lambda k:Sum((n-1)//k)*k
    return SumDivisibleBy(3)+SumDivisibleBy(5)-SumDivisibleBy(15)