题目
如果我们列出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; }
微信赞赏
支付宝赞赏