Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

The code below works & as far as I can tell the result is correct. Would you please review and let me know what I could have done better?

I tried to use variables as much as possible, that way it could easily be adapted to using other numbers instead of 3 & 5.

I learned quite a bit just writing it, and I hope I can learn more from your input!

Edit

First solution was wrong. I fixed the code and posted the new output.

<?php
/* 
** Project 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.
*/
$numberOne = 3;
$numberTwo = 5;
$endingIndex = 1000;
$multiplesOfNumbers = array();  

for ($index = 1; $index < $endingIndex; $index++) {
    if ($index % $numberOne == 0 || $index % $numberTwo == 0) {
        array_push($multiplesOfNumbers, $index);
    }
}
$sumOfMultiples = array_sum($multiplesOfNumbers);

print "The solution to Euler Project is <b>$sumOfMultiples</b> and the individual numbers are:<br><br>";
print "<pre>";
print_r($multiplesOfNumbers);
print "</pre>";
?>

Output:

For sanity check:

The solution to Euler Project is 233168 and the individual numbers are:

Array
(
    [0] => 3
    [1] => 5
    [2] => 6
    [3] => 9
    [4] => 10
    [5] => 12
    [6] => 15
    [7] => 18
    [8] => 20
    [9] => 21
    [10] => 24
    [11] => 25
    [12] => 27
    [13] => 30
    [14] => 33
    [15] => 35
    [16] => 36
    [17] => 39
    [18] => 40
    [19] => 42
    [20] => 45
    [21] => 48
    [22] => 50
    [23] => 51
    [24] => 54
    [25] => 55
    [26] => 57
    [27] => 60
    [28] => 63
    [29] => 65
    [30] => 66
    [31] => 69
    [32] => 70
    [33] => 72
    [34] => 75
    [35] => 78
    [36] => 80
    [37] => 81
    [38] => 84
    [39] => 85
    [40] => 87
    [41] => 90
    [42] => 93
    [43] => 95
    [44] => 96
    [45] => 99
    [46] => 100
    [47] => 102
    [48] => 105
    [49] => 108
    [50] => 110
    [51] => 111
    [52] => 114
    [53] => 115
    [54] => 117
    [55] => 120
    [56] => 123
    [57] => 125
    [58] => 126
    [59] => 129
    [60] => 130
    [61] => 132
    [62] => 135
    [63] => 138
    [64] => 140
    [65] => 141
    [66] => 144
    [67] => 145
    [68] => 147
    [69] => 150
    [70] => 153
    [71] => 155
    [72] => 156
    [73] => 159
    [74] => 160
    [75] => 162
    [76] => 165
    [77] => 168
    [78] => 170
    [79] => 171
    [80] => 174
    [81] => 175
    [82] => 177
    [83] => 180
    [84] => 183
    [85] => 185
    [86] => 186
    [87] => 189
    [88] => 190
    [89] => 192
    [90] => 195
    [91] => 198
    [92] => 200
    [93] => 201
    [94] => 204
    [95] => 205
    [96] => 207
    [97] => 210
    [98] => 213
    [99] => 215
    [100] => 216
    [101] => 219
    [102] => 220
    [103] => 222
    [104] => 225
    [105] => 228
    [106] => 230
    [107] => 231
    [108] => 234
    [109] => 235
    [110] => 237
    [111] => 240
    [112] => 243
    [113] => 245
    [114] => 246
    [115] => 249
    [116] => 250
    [117] => 252
    [118] => 255
    [119] => 258
    [120] => 260
    [121] => 261
    [122] => 264
    [123] => 265
    [124] => 267
    [125] => 270
    [126] => 273
    [127] => 275
    [128] => 276
    [129] => 279
    [130] => 280
    [131] => 282
    [132] => 285
    [133] => 288
    [134] => 290
    [135] => 291
    [136] => 294
    [137] => 295
    [138] => 297
    [139] => 300
    [140] => 303
    [141] => 305
    [142] => 306
    [143] => 309
    [144] => 310
    [145] => 312
    [146] => 315
    [147] => 318
    [148] => 320
    [149] => 321
    [150] => 324
    [151] => 325
    [152] => 327
    [153] => 330
    [154] => 333
    [155] => 335
    [156] => 336
    [157] => 339
    [158] => 340
    [159] => 342
    [160] => 345
    [161] => 348
    [162] => 350
    [163] => 351
    [164] => 354
    [165] => 355
    [166] => 357
    [167] => 360
    [168] => 363
    [169] => 365
    [170] => 366
    [171] => 369
    [172] => 370
    [173] => 372
    [174] => 375
    [175] => 378
    [176] => 380
    [177] => 381
    [178] => 384
    [179] => 385
    [180] => 387
    [181] => 390
    [182] => 393
    [183] => 395
    [184] => 396
    [185] => 399
    [186] => 400
    [187] => 402
    [188] => 405
    [189] => 408
    [190] => 410
    [191] => 411
    [192] => 414
    [193] => 415
    [194] => 417
    [195] => 420
    [196] => 423
    [197] => 425
    [198] => 426
    [199] => 429
    [200] => 430
    [201] => 432
    [202] => 435
    [203] => 438
    [204] => 440
    [205] => 441
    [206] => 444
    [207] => 445
    [208] => 447
    [209] => 450
    [210] => 453
    [211] => 455
    [212] => 456
    [213] => 459
    [214] => 460
    [215] => 462
    [216] => 465
    [217] => 468
    [218] => 470
    [219] => 471
    [220] => 474
    [221] => 475
    [222] => 477
    [223] => 480
    [224] => 483
    [225] => 485
    [226] => 486
    [227] => 489
    [228] => 490
    [229] => 492
    [230] => 495
    [231] => 498
    [232] => 500
    [233] => 501
    [234] => 504
    [235] => 505
    [236] => 507
    [237] => 510
    [238] => 513
    [239] => 515
    [240] => 516
    [241] => 519
    [242] => 520
    [243] => 522
    [244] => 525
    [245] => 528
    [246] => 530
    [247] => 531
    [248] => 534
    [249] => 535
    [250] => 537
    [251] => 540
    [252] => 543
    [253] => 545
    [254] => 546
    [255] => 549
    [256] => 550
    [257] => 552
    [258] => 555
    [259] => 558
    [260] => 560
    [261] => 561
    [262] => 564
    [263] => 565
    [264] => 567
    [265] => 570
    [266] => 573
    [267] => 575
    [268] => 576
    [269] => 579
    [270] => 580
    [271] => 582
    [272] => 585
    [273] => 588
    [274] => 590
    [275] => 591
    [276] => 594
    [277] => 595
    [278] => 597
    [279] => 600
    [280] => 603
    [281] => 605
    [282] => 606
    [283] => 609
    [284] => 610
    [285] => 612
    [286] => 615
    [287] => 618
    [288] => 620
    [289] => 621
    [290] => 624
    [291] => 625
    [292] => 627
    [293] => 630
    [294] => 633
    [295] => 635
    [296] => 636
    [297] => 639
    [298] => 640
    [299] => 642
    [300] => 645
    [301] => 648
    [302] => 650
    [303] => 651
    [304] => 654
    [305] => 655
    [306] => 657
    [307] => 660
    [308] => 663
    [309] => 665
    [310] => 666
    [311] => 669
    [312] => 670
    [313] => 672
    [314] => 675
    [315] => 678
    [316] => 680
    [317] => 681
    [318] => 684
    [319] => 685
    [320] => 687
    [321] => 690
    [322] => 693
    [323] => 695
    [324] => 696
    [325] => 699
    [326] => 700
    [327] => 702
    [328] => 705
    [329] => 708
    [330] => 710
    [331] => 711
    [332] => 714
    [333] => 715
    [334] => 717
    [335] => 720
    [336] => 723
    [337] => 725
    [338] => 726
    [339] => 729
    [340] => 730
    [341] => 732
    [342] => 735
    [343] => 738
    [344] => 740
    [345] => 741
    [346] => 744
    [347] => 745
    [348] => 747
    [349] => 750
    [350] => 753
    [351] => 755
    [352] => 756
    [353] => 759
    [354] => 760
    [355] => 762
    [356] => 765
    [357] => 768
    [358] => 770
    [359] => 771
    [360] => 774
    [361] => 775
    [362] => 777
    [363] => 780
    [364] => 783
    [365] => 785
    [366] => 786
    [367] => 789
    [368] => 790
    [369] => 792
    [370] => 795
    [371] => 798
    [372] => 800
    [373] => 801
    [374] => 804
    [375] => 805
    [376] => 807
    [377] => 810
    [378] => 813
    [379] => 815
    [380] => 816
    [381] => 819
    [382] => 820
    [383] => 822
    [384] => 825
    [385] => 828
    [386] => 830
    [387] => 831
    [388] => 834
    [389] => 835
    [390] => 837
    [391] => 840
    [392] => 843
    [393] => 845
    [394] => 846
    [395] => 849
    [396] => 850
    [397] => 852
    [398] => 855
    [399] => 858
    [400] => 860
    [401] => 861
    [402] => 864
    [403] => 865
    [404] => 867
    [405] => 870
    [406] => 873
    [407] => 875
    [408] => 876
    [409] => 879
    [410] => 880
    [411] => 882
    [412] => 885
    [413] => 888
    [414] => 890
    [415] => 891
    [416] => 894
    [417] => 895
    [418] => 897
    [419] => 900
    [420] => 903
    [421] => 905
    [422] => 906
    [423] => 909
    [424] => 910
    [425] => 912
    [426] => 915
    [427] => 918
    [428] => 920
    [429] => 921
    [430] => 924
    [431] => 925
    [432] => 927
    [433] => 930
    [434] => 933
    [435] => 935
    [436] => 936
    [437] => 939
    [438] => 940
    [439] => 942
    [440] => 945
    [441] => 948
    [442] => 950
    [443] => 951
    [444] => 954
    [445] => 955
    [446] => 957
    [447] => 960
    [448] => 963
    [449] => 965
    [450] => 966
    [451] => 969
    [452] => 970
    [453] => 972
    [454] => 975
    [455] => 978
    [456] => 980
    [457] => 981
    [458] => 984
    [459] => 985
    [460] => 987
    [461] => 990
    [462] => 993
    [463] => 995
    [464] => 996
    [465] => 999
)

solved

share|improve this question
    
I just realized my answer is wrong. Could not verify until now. –  Phrancis 7 hours ago
    
I fixed the code by replacing $index <= $endingIndex to $index < $endingIndex newbie mistake! Thanks @mjolka for pointing this out! –  Phrancis 7 hours ago

2 Answers 2

Let's solve a simpler problem: Find the sum of all multiples of 3 below 1000.

We have

\begin{align} 3 + 6 + 9 + 12 + \cdots + 999 &= 3 (1 + 2 + 3 + 4 + \cdots + 333) \\ &= 3 \times \frac{333 \times (333 + 1)}{2}, \end{align}

where the second line comes from the identity

\begin{align} 1 + 2 + 3 + \cdots + n = \sum_{k = 1}^n k = \frac{n(n + 1)}{2}. \end{align}

(See also Triangular number on Wikipedia.)

Now we can use the above process to find the sum of all multiples of 5 below 1000. This gets us pretty close to the solution.

The problem is, we're counting the numbers \$15, 30, 45, \ldots\$ in our count of multiples of 3, and our count of multiples of 5. So the final step would be subtracting the number of multiples of 15 from our count, giving a solution to the original question.

share|improve this answer
    
This is exactly the intended solution to the problem. Unfortunately, it is easy to brute force. Later ones increased the upper limit to try to (usually successfully) avoid this. –  Ross Millikan 3 hours ago
    
This is exactly my answer which was posted 1 hour before yours... –  Emily L. 36 mins ago
    
@EmilyL. It's the same solution, targeted at a different audience. I thought it would be more approachable for some people. Phrancis in particular mentioned in chat that he was struggling with the math in your answer. –  mjolka 17 mins ago
    
It likely is my lack of skill in math that makes your answer very difficult for me to decipher, @EmilyL. Nevertheless, I up-voted both answers and very much appreciate both of your precious time spent helping with the algorithm. –  Phrancis 12 mins ago

You're using a brute force approach with a linear time complexity in the range and linear in the number of factors i.e. \$\mathcal{O}(nk)\$ where \$n\$ is the range of numbers (1000) and \$k\$ is the number of factors to check for (2 in this problem).

Consider the sum of all numbers that are a multiples of \$k_i\$ and less than \$n\$ and let \$c_i=\lfloor\frac{n-1}{k_i}\rfloor\$ then:

\$S_i=\sum_{m=1}^{c_i}{m\cdot k_i} = k_i\cdot c_i\frac{c_i+1}{2}\$

Now the first step to the solution to the problem is:

\$\sum_{\forall i} S_i =\sum_{\forall i}{k_i\cdot c_i\frac{c_i+1}{2}} \$

But this counts numbers divisible by both \$k_j\$ and \$k_j\$ twice (as noted in comments) so we need to subtract the double counted numbers. Let \$K_\ell\$ be all pairwise products of \$k_j\$ and \$k_j\$ (in other words, \$K_\ell=k_j\cdot k_i\$) for \$i\ne j\$, then the solution is:

\$S=\sum_{\forall i}{k_i\cdot c_i\frac{c_i+1}{2}} - \sum_{\forall \ell}{K_\ell\cdot C_\ell\frac{C_\ell+1}{2}} \$ where \$C_\ell=\lfloor\frac{n-1}{K_\ell}\rfloor\$.

The time complexity is \$\mathcal{O}(k^2)\$ and as \$k\ll n\$ it is significantly faster.

As for your implementation I would use an array for all the numbers to sum the multiples of and then iterate over that in the inner loop as that avoids an explosion of the expression in the if statement. Other than that I think it looks good.

(note: Euler problem 1 is easily solvable with pen and paper)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.