Find the sum of all the multiples of 3 or 5 below 1000

Question

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. I have the following code but the answer does not match.

#include<stdio.h>
int main()
{
    long unsigned int i,sum=0;
    clrscr();
    for(i=0;i<=1000;i++)
    {
        if((i%5==0)||(i%3==0))
        {
            sum=sum+1;
        }
    }
    printf("%d\n",sum);
    getchar();
    return 0;
}

Answer 1

#include <bits/stdc++.h>
using namespace std;

int main()
{
     int i,sum=0;                    //initialize sum with 0
    for(i=0;i<1000;i++)         //run loop from 0  999 (1000 is not included) because      
                                       //we want less than 1000.  
    {
        if(i%5==0||i%3==0)             //check if it satisfy one of the 
                                       //condition either 
                                        //it divides with 5 or 3 completely 
                                        //i.e remainder0 
        {                                     
            sum+=i;                      //increment sum by that number as 
                                             //particular number 
                                             //satisfy the condition 
        }
    }
    cout<<sum;                                 //print sum the value of sum
    return 0;
}

Answer 2

I attempt the Project Euler #1: Multiples of 3 and 5. And got 60 points for that.

private static long euler1(long N) {
        long i, sum = 0;
        for (i = 3; i < N; i++) {
            if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
            }
        }
        return sum;
    }

I use Java for it and you can use this logic for C. I worked hard and find an optimal solution.

private static void euler1(long n) {
        long a = 0, b = 0, d = 0;

        a = (n - 1) / 3;
        b = (n - 1) / 5;
        d = (n - 1) / 15;

        long sum3 = 3 * a * (a + 1) / 2;
        long sum5 = 5 * b * (b + 1) / 2;
        long sum15 = 15 * d * (d + 1) / 2;
        long c = sum3 + sum5 - sum15;
        System.out.println(c);
    }

Answer 3

Think declaratively - what you want to do, rather than how you want to do.

In plain language, it boils down to exactly what the problem asks you to do:

1. Find all multiples of 3 or 5 in a certain range (in this case 1 to 1000)
2. Add them all up (aggregate sum)

In LINQ, it looks like:

Enumerable.Range(1, 1000)
            .Where(x => (x % 3 == 0) || (x % 5 == 0))
            .Aggregate((accumulate, next) => accumulate += next);

Now, you can convert this into an iterative solution - but there is nothing wrong with using a declarative solution like above - because it is more clear and succinct.

Answer 4

int main(int argc, char** argv)
{
    unsigned int count = 0;
    for(int i = 1; i < 1001; ++i)
        if(!(i % 3) && !(i % 5))
            count += i;
    std::cout << i;
    return 0;
}

Answer 5

Interesting fact of the difference in time between this 2 methods... The second method just calculate only with needed numbers and dont iterate through a loop. Example: 3 * (1+2+3+4...333) (Because 3 * 333 = 999 and 999 < 1000.

   static void Main(string[] args)
    {
        Stopwatch sw = new Stopwatch();

        Calc calculator = new Calc();
        long target = 999999999;
        sw.Start();
        Console.WriteLine("Result: " +  (calculator.calcMultipleSumFast(3,target) + calculator.calcMultipleSumFast(5, target) - calculator.calcMultipleSumFast(15, target)));
        sw.Stop();
        Console.WriteLine("Runtime: " + sw.Elapsed);
        Console.WriteLine();
        sw.Start();
        Console.WriteLine("Result: " + (calculator.calcMultiplesSum(3, 5,1000000000)));
        sw.Stop();
        Console.WriteLine("Runtime: " + sw.Elapsed);

        Console.ReadKey();
    }

    public class Calc
{
    public long calcMultiplesSum(long n1, long n2, long rangeMax)
    {
        long sum = 0;
        for (long i = 0; i < rangeMax; i++)
        {
            if ((i % n1 == 0) || (i % n2 == 0))
            {
                sum = sum + i;
            }
        }
        return sum;
    }

    public long calcMultipleSumFast(long n, long rangeMax)
    {
        long p = rangeMax / n;

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

Answer 6

It should be sum = sum + i instead of 1.

Answer 7

Using the stepping approach, you can make a version:

#include <stdio.h>

int main ( void ) {

    int sum = 0;

    for (int i = 0; i < 1000; i += 5) {
        sum += i;
    }
    for (int i = 0; i < 1000; i += 3) {
        if (i % 5) sum += i;  /* already counted */
    }
    printf("%d\n", sum);
    return 0;
}

which does a whole lot fewer modulo computations.

In fact, with a counter, you can make a version with none:

#include <stdio.h>

int main ( void ) {

    int sum = 0;
    int cnt = 6;

    for (int i = 0; i < 1000; i += 5) {
        sum += i;
    }
    for (int i = 0; i < 1000; i += 3) {
        if (--cnt == 0) cnt = 5;
        else sum += i;
    }
    printf("%d\n", sum);
    return 0;
}

Answer 8

int Sum(int N) {
long long c = 0;
    N--; //because you want it less than 1000 if less than or equal delete this line
    int n = N/3,b = N/5,u = N/15;
    c+= (n*(n+1))/2 * 3;
    c+= (b*(b+1))/2 * 5;
    c-= (u*(u+1))/2 * 15;
    return c;
}

Answer 9

Rather than using range/loop based solutions you may wish to leverage more math than brute force.

There is a simple way to get the sum of multiples of a number, less than a number.

For instance, the sum of multiples of 3 up to 1000 are: 3 + 6 + 9 + ... + 999 Which can be rewritten as: 3* ( 1 + 2 + 3 + ... + 333)

There is a simple way to sum up all numbers 1-N:

Sum(1,N) = N*(N+1)/2

So a sample function would be

unsigned int unitSum(unsigned int n)
{
    return (n*(n+1))/2;
}

So now getting all multiples of 3 less than 1000 (aka up to and including 999) has been reduced to:

3*unitSum((int)(999/3))

You can do the same for multiples of 5:

5*unitSum((int)(999/5))

But there is a caveat! Both of these count multiples of both such as 15, 30, etc It counts them twice, one for each. So in order to balance that out, you subtract once.

15*unitSum((int)(999/15))

So in total, the equation is:

sum = 3*unitSum((int)(999/3)) + 5*unitSum((int)(999/5)) - 15*unitSum((int)(999/15))

So now rather than looping over a large set of numbers, and doing comparisons, you are just doing some simple multiplication!

Answer 10

Python implementation of the problem. Short, precise and fat.

sum=0
for i in range(1000):
    if (i%3==0) or (i%5==0):
        sum=sum+i
print sum

Answer 11

You might start by iterating from 3 to 1000 in steps of 3 (3,6,9,12,etc), adding them to the sum like,

int i = 3, sum = 0;
for (; i < 1000; i += 3) {
  sum += i;
}

Then you could iterate from 5 to 1000 by 5 (skipping multiples of 3 since they've already been added) adding those values to the sum as well

for (i = 5; i < 1000; i += 5) {
  if (i % 3 != 0) sum += i;
}

Then display the sum

printf("%d\n", sum);

Answer 12

package com.venkat.test;

public class CodeChallenge {

    public static void main(String[] args) {

        int j, sum=0;

        for ( j = 0; j <=1000; j++) {               
            if((j%5==0)||(j%3==0))
            {
                sum=sum+j;
            }               
        }           
        System.out.println(sum);            
    }    
}

Answer 13

Just as an improvement you might want to avoid the loop altogether :

multiples of 3 below 1000 form an AP : 3k where k in [1, 333]
multiples of 5 below 1000 form an AP : 5k where k in [1, 199]

If we avoid multiples of both 3 and 5 : 15k where k in [1, 66]

So the answer is : 333*(3+999)/2 + 199(5+995)/2 - 66*(15+990)/2 = 233168

Why you might want to do this is left to you to figure out.

Answer 14

#include<stdio.h>
#include<time.h>
int main()
{
    int x,y,n;
    int sum=0;
    printf("enter the valeus of x,y and z\n");
    scanf("%d%d%d",&x,&y,&n);
    printf("entered   valeus of x=%d,y=%d and z=%d\n",x,y,n);
    sum=x*((n/x)*((n/x)+1)/2)+y*((n/y)*((n/y)+1)/2)-x*y*(n/(x*y))*((n/(x*y))+1)/2;
    printf("sum is %d\n",sum);
    return 0;
}
// give x,y and n  as 3 5 and 1000

Answer 15

Here's a python one-liner that gives the correct answer (233168):

reduce( lambda x,y: x+y, [ x for x in range(1000) if x/3.0 == int( x/3.0 ) or x/5.0 == int( x/5.0 ) ] )

Answer 16

Two things:

• you're including 1000 in the loop, and
• you're adding one to the sum each time, rather than the value itself.

Change the loop to

for(i=0;i<1000;i++)

And the sum line to

sum=sum+i;

Answer 17

Perhaps you should do

sum += i // or sum = sum + i

instead of

sum = sum + 1

Additionally, be careful when printing long unsigned ints with printf. I guess the right specifier is %lu.