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

2 Responses to “Project Euler: Problem 1”

  1. Tavis Says:

    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.

  2. Tavis Says:

    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;
    }

Leave a Reply