Sieve of Eratosthenes

Definition

The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to a specified value.

Algorithm

  1. First, strike off all multiples of 2 greater than 2 from the list.
  2. The next lowest (uncrossed off) number in the list is prime and now strike of all multiples of this number.
  3. Repeat step #2 until you reach a number greater than the square root of the highest number in the list.
  4. All the remaining numbers are prime.

Code

public static void sieve(int[] x){
  for (int i = 2; i < Math.sqrt(x.length); i++) {
    multiples(x,i);
  }
}
 
public static void multiples(int[] x, int n) {
  for (int i = 2*n-1; i < x.length; i+=n) {
    x[i] = 0;
  }
}

Visual

flickr:3028829924

Animation

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License