Sum of numbers under 10,000 that are multiples of

问题:

I know how to get the program to add up the sums of the multiple for each of 3, 5 and 7, but I'm not sure how I'd get the program to only use each number once. For example, I can get the program to find out all of the numbers and add them up for 3 and then do the same for 5, but then the number 15 would be in the final number twice. I'm not sure exactly how I'd get it to only take the number once. Thanks for any help.

回答1:

The easiest approach would be to use a for loop thus:

int sum = 0;
for(int i=1; i<10000; i++)
{
    if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
        sum += i;
}

回答2:

While the generate-and-test approach is simple to understand, it is also not very efficient if you want to run this on larger numbers. Instead, we can use the inclusion-exclusion principle.

The idea is to first sum up too many numbers by looking at the multiples of 3, 5 and 7 separately. Then we subtract the ones we counted twice, i.e. multiples of 3*5, 3*7 and 5*7. But now we subtracted too much and need to add back the multiples of 3*5*7 again.

We start by finding the sum of all integers 1..n which are multiples of k. First, we find out how many there are, m = n / k, rounded down thanks to integer division. Now we just need to sum up the sequence k + 2*k + 3*k + ... + m*k. We factor out the k and get k * (1 + 2 + ... + m).

This is a well-known arithmetic series, which we know sums to k * m * (m + 1)/2 (See triangle number).

private long n = 9999;
private long multiples(long k) {
    long m = n / k;
    return k * m * (m + 1) / 2:
}

Now we just use inclusion-exclusion to get the final sum:

long sum = multiples(3) + multiples(5) + multiples(7)
         - multiples(3*5) - multiples(3*7) - multiples(5*7)
         + multiples(3*5*7);

This will scale much better to larger n than just looping over all the values, but beware of overflow and change to BigIntegers if necessary.

回答3:

Use a Set to store the unique multiples, and then sum the values of the Set.

回答4:

I would use a Set. This way you are guaranteed that you won't get any duplicates if they are your main problem.

回答5:

One simple solution would be to add each number thats a multiple of 3,5, or 7 to an Answer list. And then as you work thru each number, make sure that its not already in the answer list.

(pseudo-code)

List<int> AnswerList;
List<int> MultiplesOfFive;
List<int> MultiplesOfSeven;
List<int> MultiplesOfThree;

for (int i = 0 ; i < 10000; i++)
{
  if ( i % 3 == 0 && AnswserList.Contains(i) == false)
  {
    MultiplesOfThree.Add(i); 
    AnswerList.Add(i);
  }
  if ( i % 5 == 0 && AnswserList.Contains(i) == false)
  {
    MultiplesOfFive.Add(i); 
    AnswerList.Add(i);
  }
  if ( i % 7 == 0 && AnswserList.Contains(i) == false)
  {
    MultiplesOfSeven.Add(i); 
    AnswerList.Add(i);
  }
}

回答6:

for the solution that loops 1 to 1000 use i<=10000 otherwise it'll skip 10000 itself which is a multiple of 5. Apologies, for some reason i can't post this as a comment