simple C problem

Question

I have had to start to learning C as part of a project that I am doing. I have started doing the 'euler' problems in it and am having trouble with the first one. I have to find the sum of all multiples of 3 or 5 below 1000. Could someone please help me. Thanks.

#include<stdio.h>
int start;
int sum;

int main() {
    while (start < 1001) {
        if (start % 3 == 0) {
            sum = sum + start;
            start += 1;
        } else {
            start += 1;
        }

        if (start % 5 == 0) {
            sum = sum + start;
            start += 1;
        } else {
            start += 1;
        }
        printf("%d\n", sum);
    }
    return(0);
}

Answer 1

You've gotten some great answers so far, mainly suggesting something like:

#include <stdio.h>
int main(int argc, char * argv[])
{
  int i;
  int soln = 0;
  for (i = 1; i < 1000; i++)
  {
    if ((i % 3 == 0) || (i % 5 == 0))
    {
      soln += i;
    }
  }
  printf("%d\n", soln);
  return 0;
}

So I'm going to take a different tack. I know you're doing this to learn C, so this may be a bit of a tangent.

Really, you're making the computer work too hard for this :). If we figured some things out ahead of time, it could make the task easier.

Well, how many multiples of 3 are less than 1000? There's one for each time that 3 goes into 1000 - 1.

mult₃ = ⌊ (1000 - 1) / 3 ⌋ = 333

(the ⌊ and ⌋ mean that this is floor division, or, in programming terms, integer division, where the remainder is dropped).

And how many multiples of 5 are less than 1000?

mult₅ = ⌊ (1000 - 1) / 5 ⌋ = 199

Now what is the sum of all the multiples of 3 less than 1000?

sum₃ = 3 + 6 + 9 + ... + 996 + 999 = 3×(1 + 2 + 3 + ... + 332 + 333) = 3×∑_{i=1 to mult3} i

And the sum of all the multiples of 5 less than 1000?

sum₅ = 5 + 10 + 15 + ... + 990 + 995 = 5×(1 + 2 + 3 + ... + 198 + 199) = 5×∑_{i = 1 to mult5} i

Some multiples of 3 are also multiples of 5. Those are the multiples of 15. Since those count towards mult₃ and mult₅ (and therefore sum₃ and sum₅) we need to know mult₁₅ and sum₁₅ to avoid counting them twice.

mult₁₅ = ⌊ (1000 - 1) /15 ⌋ = 66

sum₁₅ = 15 + 30 + 45 + ... + 975 + 990 = 15×(1 + 2 + 3 + ... + 65 + 66) = 15×∑_{i = 1 to mult15} i

So the solution to the problem "find the sum of all the multiples of 3 or 5 below 1000" is then

soln = sum₃ + sum₅ - sum₁₅

So, if we wanted to, we could implement this directly:

#include <stdio.h>
int main(int argc, char * argv[])
{
  int i;
  int const mult3 = (1000 - 1) / 3;
  int const mult5 = (1000 - 1) / 5;
  int const mult15 = (1000 - 1) / 15;
  int sum3 = 0;
  int sum5 = 0;
  int sum15 = 0;
  int soln;

  for (i = 1; i <= mult3; i++) { sum3 += 3*i; }
  for (i = 1; i <= mult5; i++) { sum5 += 5*i; }
  for (i = 1; i <= mult15; i++) { sum15 += 15*i; }

  soln = sum3 + sum5 - sum15;
  printf("%d\n", soln);
  return 0;
}

But we can do better. For calculating individual sums, we have Gauss's identity which says the sum from 1 to n (aka ∑_{i = 1 to n} i) is n×(n+1)/2, so:

sum₃ = 3×mult₃×(mult₃+1) / 2

sum₅ = 5×mult₅×(mult₅+1) / 2

sum₁₅ = 15×mult₁₅×(mult₁₅+1) / 2

(Note that we can use normal division or integer division here - it doesn't matter since one of n or n+1 must be divisible by 2)

Now this is kind of neat, since it means we can find the solution without using a loop:

#include <stdio.h>
int main(int argc, char *argv[])
{
  int const mult3 = (1000 - 1) / 3;
  int const mult5 = (1000 - 1) / 5;
  int const mult15 = (1000 - 1) / 15;
  int const sum3 = (3 * mult3 * (mult3 + 1)) / 2;
  int const sum5 = (5 * mult5 * (mult5 + 1)) / 2;
  int const sum15 = (15 * mult15 * (mult15 + 1)) / 2;

  int const soln = sum3 + sum5 - sum15;
  printf("%d\n", soln);
  return 0;
}

Of course, since we've gone this far we could crank out the entire thing by hand:

sum₃ = 3×333×(333+1) / 2 = 999×334 / 2 = 999×117 = 117000 - 117 = 116883

sum₅ = 5×199×(199+1) / 2 = 995×200 / 2 = 995×100 = 99500

sum₁₅ = 15×66×(66+1) / 2 = 990×67 / 2 = 495 × 67 = 33165

soln = 116883 + 99500 - 33165 = 233168

And write a much simpler program:

#include <stdio.h>
int main(int argc, char *argv[])
{
  printf("233168\n");
  return 0;
}

Answer 2

You have forgotten to initialize your variables,

Answer 3

Here's a general solution which works with an arbitrary number of factors:

#include <stdio.h>

#define sum_multiples(BOUND, ...) \
    _sum_multiples(BOUND, (unsigned []){ __VA_ARGS__, 0 })

static inline unsigned sum_single(unsigned bound, unsigned base)
{
    unsigned n = bound / base;
    return base * (n * (n + 1)) / 2;
}

unsigned _sum_multiples(unsigned bound, unsigned bases[])
{
    unsigned sum = 0;

    for(unsigned i = 0; bases[i]; ++i)
    {
        sum += sum_single(bound, bases[i]);

        for(unsigned j = i + 1; bases[j]; ++j)
            sum -= sum_single(bound, bases[i] * bases[j]);
    }

    return sum;
}

int main(void)
{
    printf("%u\n", sum_multiples(999, 3, 5));
    return 0;
}

Answer 4

Eh right, well i can see roughly where you are going, I'm thinking the only thing wrong with it has been previously mentioned. I did this problem before on there, obviously you need to step through every multiple of 3 and 5 and sum them. I did it this way and it does work:

int accumulator = 0;
int i;

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

for (i = 0; i < 1000; i +=5) {
    if (!(i%3==0)) {
        accumulator += i;
    }
}
printf("%d", accumulator);

EDIT: Also note its not 0 to 1000 inclusive, < 1000 stops at 999 since it is the last number below 1000, you have countered that by < 1001 which means you go all the way to 1000 which is a multiple of 5 meaning your answer will be 1000 higher than it should be.

Answer 5

The answers are all good, but won't help you learn C.

What you really need to understand is how to find your own errors. A debugger could help you, and the most powerful debugger in C is called "printf". You want to know what your program is doing, and your program is not a "black box".

Your program already prints the sum, it's probably wrong, and you want to know why. For example:

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

instead of

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

and save it into a text file, then try to understand what's going wrong.

• does the count start with 1 and end with 999?
• does it really go from 1 to 999 without skipping numbers?
• does it work on a smaller range?

Answer 6

The problem with your code is that your incrementing the 'start' variable twice. This is due to having two if..else statements. What you need is an if..else if..else statement as so:

           if  (start % 3 == 0) {
                    sum = sum + start;
                    start += 1;
            }
            else if (start % 5 == 0) {
                    sum = sum + start;
                    start += 1;
            }
            else {
                    start += 1;
            }

Or you could be more concise and write it as follows:

if(start % 3 == 0)
    sum += start;
else if(start % 5 == 0)
    sum += start;
start++;

Either of those two ways should work for you.

Good luck!

Answer 7

Really you need a debugger, and to single-step through the code so that you can see what it's actually doing. Your basic problem is that the flow of control isn't going where you think it is, and rather than provide correct code as others have done, I'll try to explain what your code does. Here's what happens, step-by-step (I've numbered the lines):

1:    while (start < 1001) {
2:        if  (start % 3 == 0) {
3:            sum = sum + start;
4:            start += 1;
5:        }
6:        else {
7:            start += 1;
8:        }
9:
10:       if (start % 5 == 0) {
11:           sum = sum + start;
12:           start += 1;
13:       }
14:       else {
15:           start += 1;
16:       }
17:       printf("%d\n", sum);
18:    }

• line 1. sum is 0, start is 0. Loop condition true.
• line 2. sum is 0, start is 0. If condition true.
• line 3. sum is 0, start is 0. sum <- 0.
• line 4. sum is 0, start is 0. start <- 1.
• line 5. sum is 0, start is 1. jump over "else" clause
• line 10. sum is 0, start is 1. If condition false, jump into "else" clause.
• line 15. sum is 0, start is 1. start <- 2.
• line 16 (skipped)
• line 17. sum is 0, start is 2. Print "0\n".
• line 18. sum is 0, start is 2. Jump to the top of the loop.
• line 1. sum is 0, start is 2. Loop condition true.
• line 2. sum is 0, start is 2. If condtion false, jump into "else" clause.
• line 7. sum is 0, start is 2. start <- 3.
• line 10. sum is 0, start is 3. If condition false, jump into "else" clause.
• line 15. sum is 0, start is 3. start <- 4.
• line 17. sum is 0, start is 4. Print "0\n".

You see how this is going? You seem to think that at line 4, after doing sum += 1, control goes back to the top of the loop. It doesn't, it goes to the next thing after the "if/else" construct.

Answer 8

You would be much better served by a for loop, and combining your conditionals.

Not tested:

int main()
{
  int x;
  int sum = 0;

  for (x = 1; x <= 1000; x++)
    if (x % 3 == 0 || x % 5 == 0)
      sum += x;

  printf("%d\n", sum);
  return 0;
}

Answer 9

You could change your ifs:

 if  ((start % 3 == 0) || (start % 5 == 0)) 
     sum += start;
 start ++;

and don´t forget to initialize your sum with zero and start with one. Also, change the while condition to < 1000.

Answer 10

You haven't said what the program is supposed to do, or what your problem is. That makes it hard to offer help.

At a guess, you really ought to initialize start and sum to zero, and perhaps the printf should be outside the loop.