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

题目

如果我们列出10以下的3和5的倍数,我们可以得到3,5,6,9。它们的和为23。请求出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;
}
赞赏

微信赞赏支付宝赞赏

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注