## 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.

Click “More” for my solution.

I decided on a quick and simple brute force approach. There are clearly many more efficient ways of doing this, however the code below solves the problem in reasonable time.

The timings were taken on a *Genuine Intel(R) CPU U1400 @ 1.20GHz *with* 1GB RAM*.

Code:

#include int inc(int num) { num++; if (((num % 3) ==0) || ((num % 5) ==0)) return num; else return inc(num); } int main() { int sum; int i; sum = 0; for (i = 3; i < 1000; i = inc(i)) { sum += i; } printf("%dn", sum); return 0; }

Timings:

$ time ./1 233168 real 0m0.002s user 0m0.004s sys 0m0.000s

January 1st, 2008 at 2:05 am

I also started off with brute force, but soon realized that we just need to take 15, the lcm of 3 and 5, take the 1000/15th triangle number then multiple that by 15.

#include

int Tn(int n) {

return (n*(n + 1))/2;

}

int main() {

int lcm = 15;

int n = 1000;

printf(“%d”, Tn(n/lcm)*lcm);

return 0;

}

This is orders of magnitude faster for higher values of n.

January 1st, 2008 at 9:28 am

oops, I misread the 3 OR 5 to be 3 AND 5. Here’s the corrected version.

#include stdio.h

int Tn(int n) {

return (n*(n + 1))/2;

}

int msum(int n, int factor) {

return Tn(n/factor)*factor;

}

int main() {

int n = 999;

printf(“%d”, (msum(n,3)+msum(n,5))-msum(n,15));

return 0;

}