Sum of numbers less than 10,000, multiples of 3, 5 or 7 in Java

Question

I know how to get a program to sum sums of several for each of 3, 5 and 7, but I'm not sure how to get the program to use only one number of times. For example, I can get a program to find out all the numbers and add them for 3, and then do the same for 5, but then the number 15 will be in the last number twice. I don’t know exactly how I would receive it only once. Thanks for any help.

Answer 1

The easiest way is to use a for loop like this:

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

Answer 2

While the generation and testing approach is easy to understand, it is also not very effective if you want to run it on large numbers. Instead, we can use the inclusion-exclusion principle.

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

We start by finding the sum of all integers 1..n that are multiples of k . Firstly, we will find out how many of them, m = n / k , are rounded due to integer division. Now we just need to sum the sequence k + 2*k + 3*k + ... + m*k . We define k and get k * (1 + 2 + ... + m) .

This is a well-known arithmetic series, which, as we know, is the sum of 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 the inclusion exception to get the final amount:

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

This will improve significantly to a larger n than just a loop over all values, but beware of overflows and change to BigInteger if necessary.

Answer 3

Use Set to store unique multiple values, and then sum the Set values.

Answer 4

I would use Set . Thus, you are guaranteed that you will not get duplicates if this is your main problem.

Answer 5

One simple solution would be to add each number multiple of 3.5 or 7 to the answer list. And then, when you work on each number, make sure that it is not yet in the list of answers.

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

Answer 6

for a solution that works from 1 to 1000, I use <= 10000, otherwise it will skip 10000, which is a multiple of 5. Apologies, for some reason I can not post this as a comment