Project Euler

A Taste of Number Theory

Problem 1: Multiples of 3 and 5

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.


The Catch

How to check if an arbitrary number x is evenly divisible by 3 or 5.

The Light

To check for divisibility, use modulus operation (%), which calculates the remainder of x divides by a, where a != 0. If x % a == 0, then the division of x by a leaves no remainder, or x is divisible by a (In Discrete Mathematics, this is written as x | a).

The Code

public class Problem1 {
  public static void main(String[] args) {
    int sum = 0;
    for(int i = 0; i < 1000; i++) { 
      if(i % 3 == 0 || i % 5 == 0)
        sum += i;
    }
    System.out.println(sum);
  }
}