PrjEulr 1---求出1000以内所有的能被3或5整除的数的和

waynebuaa

原文：
         If we list all the natural numbers below 10 that are multiples of 3or 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.

译文：
         求出1000以内所有的能被3或5整除的数的和


看看大家有没有什么比较不错的方法。

[ 本帖最后由 waynebuaa 于 2008-12-7 12:24 编辑 ]

waynebuaa

如果从算法上考虑的话，以上的方法时间的复杂程度都是指数的，下面的方法时间复杂程度为多项式：

1. n = 1000;
   
2. Sum[3 i, {i, 1, Floor[n/3]}] + Sum[5 i, {i, 1, Floor[n/5]}] -
   
3. Sum[15 i, {i, 1, Floor[n/15]}]

复制代码

waynebuaa

欧拉计划的宗旨：
1、解出答案来
2、通过对比，评出最快的算法或代码。



补充说明：
1、大家不妨在编代码时，先这样想：“不管白猫黑猫，我要的是能得到答案”。
首先做到这一步。觉得有余力了，可以试着给出更优的代码。

2、相信不同的人，思路不一样，给出的代码也会不同，这时，
我们大家可以进行一下性能评比。于是，这第二步自然就在大家的共同参与下实现了。

3、如果以上过程都走完了，我想，各个经验层次的人都会得到锻炼的。

[ 本帖最后由 waynebuaa 于 2008-12-7 12:51 编辑 ]

changqing

1. Total[Select[Range[1000],Divisible[#,3]||Divisible[#,5]&]]

复制代码

waynebuaa

:victory:

1. Cases[Range[10000], x_ /; Divisible[x, 3] || Divisible[x, 5]] // Total

复制代码

jimogsh

楼上一下给出这么优秀的答案别人还怎么混 啊

waynebuaa

你试试用你前几天的那个For结构里的缺省If来实现看看

marveloustau

1. In[63]:= ClearSystemCache[];
   
2. 
   
3. {Timing@Total[
   
4. 
   
5.    Select[Range[1000000], Divisible[#, 3] || Divisible[#, 5] &]], (*Changqing's, 控制组*)
   
6. 
   
7. Timing@Total[
   
8. 
   
9.    Select[Range[1000000], Mod[#, 3] == 0 || Mod[#, 5] == 0 &]], (*将控制组的Divisible换成了Mod，对照组1*)
   
10. 
    
11. Timing@(Plus @@
    
12. 
    
13.     Select[Range[1000000], Divisible[#, 3] || Divisible[#, 5] &]), (*将控制组Total换成了Plus，对照组2*)
    
14. 
    
15. Timing@Total[
    
16. 
    
17.    Cases[Range[1000000], x_ /; Divisible[x, 3] || Divisible[x, 5]]], (*Wayne's，对照组3*)
    
18. 
    
19. Timing@(Plus @@
    
20. 
    
21.     Map[If[Divisible[#, 3] || Divisible[#, 5], #, 0] &,
    
22. 
    
23.      Range[1000000]])} (*Tau's，对照组4*)
    
24. 
    
25. 
    
26. 
    
27. Out[64]= {{3.276, 233334166668}, {4.369, 233334166668}, {2.854,
    
28. 
    
29.   233334166668}, {2.871, 233334166668}, {4.071, 233334166668}}

复制代码

[实验结果]
1.结果是233334166668。
2.由Select+真值函数测试的性能表现略逊于由Cases+谓词测试(控制组与对照组3)，而Map+If的性能最差(对照组4，可以想到如果用了Total会更慢)
3.Plus的性能优于Total。
4.Divisible[]的性能优于Mod[]==0

[讨论]
你们为啥不人为设置一个更紧的Constraint呢？

1. In[60]:= Timing@(Plus @@ Union[3 Range[333333], 5 Range[200000]])
   
2. 
   
3. Out[60]= {0.733, 233334166668}

复制代码

jimogsh

我的成果，大家不要取笑

1. tot = 0;
   
2. For[i = 1, i <= 1000,
   
3.   If[Divisible[i, 3] == True || Divisible[i, 5] == True,
   
4.    tot = tot + i], i++];
   
5. tot

复制代码

[ 本帖最后由 jimogsh 于 2008-12-7 15:28 编辑 ]

jimogsh

答案不是234168吗，为什么我在欧拉计划那网站上输入答案提示是错的

changqing

我的结果有些不一样：

1. In[1]:= ClearSystemCache[];
   
2. {Timing@Total[
   
3.    Select[Range[1000000],
   
4.     Divisible[#, 3] || Divisible[#, 5] &]],(*Changqing's,控制组*)
   
5. Timing@Total[
   
6.    Select[Range[1000000],
   
7.     Mod[#, 3] == 0 || Mod[#, 5] == 0 &]],(*将控制组的Divisible换成了Mod，对照组1*)
   
8. Timing@(Plus @@
   
9.     Select[Range[1000000],
   
10.      Divisible[#, 3] || Divisible[#, 5] &]),(*将控制组Total换成了Plus，对照组2*)
    
11. Timing@Total[
    
12.    Cases[Range[1000000],
    
13.     x_ /; Divisible[x, 3] || Divisible[x, 5]]],(*Wayne's，对照组3*)
    
14. Timing@(Plus @@
    
15.     Map[If[Divisible[#, 3] || Divisible[#, 5], #, 0] &,
    
16.      Range[1000000]])} (*Tau's，对照组4*)
    
17. Out[2]= {{2.122, 233334166668}, {3.057, 233334166668}, {2.403,
    
18.   233334166668}, {2.309, 233334166668}, {3.525, 233334166668}}

复制代码

marveloustau

{{3.182, 233334166668}, {4.478, 233334166668}, {3.042,
  233334166668}, {3.057, 233334166668}, {4.665, 233334166668}}

或许是结果的随机程度超过了精度...

waynebuaa

你好像没把那个For程序的精髓完全吸收哦！:victory:

1. For[s = 0; i = 1, i <= 1000,
   
2. If[Divisible[i, 3] || Divisible[i, 5], s += i] i++]; s

复制代码

waynebuaa

我的机子运行的时间为：

1. {{9.584, 233334166668},
   
2. {14.441, 233334166668}, {10.074, 233334166668},
   
3. {9.774, 233334166668}, {13.329, 233334166668}}

复制代码

而我最后给的程序运行的时间为：

{1.702, 233334166668}

[ 本帖最后由 waynebuaa 于 2008-12-7 19:05 编辑 ]

waynebuaa

原帖由 jimogsh 于 2008-12-7 15:22 发表
答案不是234168吗，为什么我在欧拉计划那网站上输入答案提示是错的

我明白了，If we list all the natural numbers below 10 that are multiples of 3 or5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

意思是说，不包括1000这个数，正确结果应该为：

233168

bainhome

用MATLAB凑个热闹：

1. >> Ans=sum(unique([3:3:999,5:5:999]))
   
2. Ans =
   
3.       233168

复制代码

waynebuaa

看图片吧：

jimogsh

是这样的，我把tot=0写在最前面是因为我确实还没有明白For循环中分号和逗号的区别以及引起的不同后果，而Divisible[i,3]==0这种写法只是因为我从来没有用过Divisible这个函数，今天刚学的，难免做的不够好，呵呵
学习中……
看了一下，12楼的帖子确实是目前最简单的，我也曾想到利用15怎么算的，可惜没做出来。其实我那个几乎就是看楼上的几个贴子抄过来的，不过自己也是进行了一些思考的，呵呵

[ 本帖最后由 jimogsh 于 2008-12-7 21:35 编辑 ]

changqing

仿照bainhome的代码，速度超快：

1. 
   
2. In[3]:= Timing@Total@Union[Range[3, 999999, 3], Range[5, 999999, 5]]
   
3. 
   
4. Out[3]= {0.421, 233333166668
   

复制代码

waynebuaa

我在上面的图片里已经展示出了两个速度最快的代码：

1. n = 10^6 - 1;

复制代码

tau兄的：

1. Timing@Total@Union[3 Range[Floor[n/3]], 5 Range[Floor[n/5]]]

复制代码

我的：

1. Timing[Sum[3 i, {i, 1, Floor[n/3]}] + Sum[5 i, {i, 1, Floor[n/5]}]-Sum[15 i, {i, 1, Floor[n/15]}]]

复制代码

不过，在对待Range上，第一个代码跟你的不同，速度你快了一点，因为你的少做了很多乘法。

第二个代码比你的慢一点，受你的影响，我去掉了不必要的乘法，则速度马上就提高了一倍，又比你快了很多了：

1. Timing[Sum[i, {i, 3, n, 3}] + Sum[i, {i, 5, n, 5}]-Sum[i, {i, 15, n, 15}]]

复制代码

[ 本帖最后由 waynebuaa 于 2008-12-7 23:31 编辑 ]