欧拉计划：找出1000以下3与5的倍数之和

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.

原文链接

https://projecteuler.net/problem=1

解答

我会用php，python，以及c来解答这个题目。

初看起来似乎很简单，用普通程序员最直观的观点就是使用整除运算，能够被3或者5整除，那么就累加。直接算出结果，这实在是太简单了。

没错，上面的确实能够求出来，而且以计算机的速度，求1000以下的3和5的倍数之和，运算量实在是太小了。但是这却是最低效的解决方法。

一个比较好的解决方法是什么呢？

仔细一看，3和5倍数，那不就是一个等差数列嘛！好了，这就是关键了。

其中3,6,9,12…构成一个以3为差的等差数列。5,10,15,20….构成一个以5为差的等差数列，但是，请注意，3和5的公倍数为15，也就是说，两个数列会有一个以15位差的等差数列重合。因此求和的时候要减去！

还有一个，1000以下，那便是不包括1000。

php代码示例

<?php
/**
 * 如果我们列出10以下的3和5的倍数，我们可以得到3,5,6,9。它们的和为23。
 * 请求出1000以下所有的3和5的倍数之和。
 */
function sumcount($a1){
    $n = (int)(999/$a1);
    $an = $a1+$a1*($n-1);
    return $n*($a1+$an)/2;
}

echo sumcount(5)+sumcount(3)-sumcount(15);

python代码示例

#coding:utf-8

'''
如果我们列出10以下的3和5的倍数，我们可以得到3,5,6,9。它们的和为23。
请求出1000以下所有的3和5的倍数之和。
'''

def sumcount(a1):
    n = (int)(999/a1)
    an = a1+a1*(n-1)
    return n*(a1+an)/2

print( sumcount(3) + sumcount(5) - sumcount(15))

c代码示例

/**
 * 如果我们列出10以下的3和5的倍数，我们可以得到3,5,6,9。它们的和为23。
 * 请求出1000以下所有的3和5的倍数之和。
 */
#include <stdio.h>

int sumcount(int a1);

int main(){
    printf("%d",sumcount(3)+sumcount(5)-sumcount(15));
    return 0;
}

int sumcount(int a1){
    int an,n;
    n = (int)(999/a1);
    an = a1+a1*(n-1);
    return n*(a1+an)/2;
}