Euler 001- Starting out Easy
At least something to start the blog with.
Project Euler problem #1; sum all natural numbers less then 1000 that are multiples of 3 or 5. Natural numbers meaning positive integers. The simplest way to go about this is a for loop with a sum, something akin to:
int sum=0; for(int i=1; i<1000; i++) if(i%3==0 || i%5==0) sum+=i; Console.WriteLine(sum); |
Which gives us a nice and specific answer, which is correct. Fun optimization side of this:
You can consider the sum of all 3’s to be 3*sum(1..333), which can be computed as 3*(333*332/2 + 333), if math holds.
Similarly, sum of 5 is 5*sum(1..199) = 5*(199*198/2 + 199).
Next, you need to determine the sum of natural numbers divisible by 15: 15*sum(1..66)=15*67*66/2;
Finally, take the sum of the first two values, and subtract from that the last value. In this case: 166833 + 99500 – 33165 = the answer. This follows from a little too much math, and a bit of set theory: numbers divisible by 15 are counted in both the 3 and 5 cases, effectively double counted. We subtract one of these double counts to end up with a single count of all numbers; and, an O(1) solution.
Tags: project euler
