Project Euler 1 in Java

Question

I have following exercise:

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.

So I wrote below code which finds the sum of all multiples of 3 or 5 below 1000.

Main.java:

package pl.hubot.projecteuler.problem1;
public class Main {
 public static void main(String[] args) {
 int sum = 0;
 for (int i = 1; i < 1000; i++) {
 if (i % 3 == 0 || i % 5 == 0) sum += i;
 }
 System.out.print(sum);
 }
}

How it code works?

I declared sum variable, iterated through i = 1 to i = 999 and if i is multiply of 3 or 5 then I add it to the sum. Finally, I printed out the sum variable.

Questions

• Is it a efficient method to solve this exercise?
• How can I simplify code?
• How can I increase performance of this code?

• Tyler Durden: Project Euler allows users to submit their code, so you can read the solutions of other people (once you solve the problem).
• styps: Something you might find interesting for such tasks is the IntStream class introduced in Java 8
• Jörg W Mittag: Many Project Euler problems have mathematical solutions, rather than algorithmic ones. I don't find them good as programming exercises, to be honest. They are more math exercises to me.
• styps: @JörgWMittag agreed, there are more programming-oriented resources out there; however: PE problems usually are solvable in two ways: You can either use brute force, or you can take a step back and think deeper about the problem and look for smarter ways. If that's not a valuable lesson for programmers as well, I don't know what is
• Jörg W Mittag: @styks: You're right. There are other similar sites, where you don't submit the answer, but rather submit the code and they run the code on the server, under a (typically rather strict) time limit, which pretty much forces you towards the mathematical solution.

Answer 1

I think it is very concise, well done!

For this small problem this will be fast enough.

Code only

I would only add braces around the if body:

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

For performance, please note that modulo is kind of slow. You could implement two variables that hold multiples of 3 and 5.

 public static void main(String[] args) {
 int threes = 0;
 int fives = 0;
 int sum = 0;
 for (int i = 1; i < 1000; i++) {
 if (i>threes)
 threes+=3;
 if (i>fives)
 fives+=5;
 if (i == threes || i == fives )
 sum+=i;
 }
 System.out.print(sum);
 }

Math

Better will be to go purely mathemathical:

The formula for the sum of an arithmetic series is:

Sn = (n/2) * (a₁ + a_n)

Sn = the sum of the n terms in the sequence.

a₁ = the first term in the sequence.

a_n = the nth term in the sequence.

We need to determine the number of items 'n' in the sequence. For simplicity I name this occurrences.

This is calculated as dividing the limit - 1 by number. Because the integer division, it is rounded down.

The number a_n is the last multiple that fits below the limit, which is equal to occurrences * number

Calculate the sum om the series for threes, fives and fifteens. The solution is:

Sum(threes) + Sum(fives) - Sum(fifteens)

In code:

public static int sum( int limit, int number )
{
 int occurrences = (limit-1) / number;
 //Below is a rewrite ( thnx to Olivier Grégoire) of:
 // (int) ( ( occurrences / 2.0 ) * ( occurrences * number + number) );
 return number * occurrences * (occurrences + 1) / 2;
}
public static void main( String[] args )
{
 System.out.println( sum(1000,3) + sum(1000,5) - sum(1000, 15));
}

• Olivier Grégoire: Why the abuse of parentheses? I would rewrite int occurrences = (limit - 1) / number; return number * occurrences * (occurrences + 1) / 2;. No useless doubles (and subsequent cast), less barely readable parentheses. The priority of operations does all the rest.
• Rob Audenaerde: The occurrences line is surely correct (I edited it), but are you sure about the rounding in the second?
• Olivier Grégoire: occurrences is either odd or even. occurrences + 1 is the opposite. When you multiply them both, you always have an even number, which you can safely divide by 2 without any rounding at all.
• Rob Audenaerde: Ah and because even * (maybe uneven) number is even too, it will work. Thanks! Will edit it in.

Answer 2

Consider generating multiples of 3 or 5 that way you avoid needing to do % 3 or % 5

Other than that the code is neat and about as simple as you can get really.