#header-inner {background-position: right !important; width: 100% !important;}

9/17/12

Sieve of Eratosthenes.

In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit.

Sieve of Eratosthenes in action., In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit.
Source code:

package eratosthenes.sieve;

import java.util.Collection;
import java.util.Iterator;
import java.util.TreeSet;

public class EratosthenesSieve {
  private int limit;
  private Collection numbers = new TreeSet();

  public EratosthenesSieve(int limit) {
    this.limit = limit;
    repopulateNumbers(limit);
  }

  public void sieve() {
    for (int i=2; i<=this.limit; i++) {
      if (numbers.contains(new Integer(i))) {
        removeMultiplicationsOf(i);
      }
    }
  }

  public void repopulateNumbers(int max) {
    numbers.clear();
    for (int i = 2; i<=max; i++) {
      numbers.add(new Integer(i));
    }
  }

  public String toString() {
    final StringBuilder sb = new StringBuilder();
    final Iterator it = numbers.iterator();
    if (it.hasNext()) {
      sb.append(it.next());
    }
    while (it.hasNext()) {
      sb.append(" ");
      sb.append(it.next());
    }
    return sb.toString();
  }

  private void removeMultiplicationsOf(int n) {
    int i=2;
    while(i * n <= this.limit) {
      numbers.remove(new Integer(i * n));
      i = i + 1;
    }
  }

  public static void main(String[] args) {
    final EratosthenesSieve eratosthenesSieveInstance = new EratosthenesSieve(84);
    System.out.println(eratosthenesSieveInstance.toString());
    eratosthenesSieveInstance.sieve();
    System.out.println(eratosthenesSieveInstance.toString());
  }
}

1 comment:

  1. Eratosthenes is not Erastothenes. I do not want to call him Erastoosiemthenes ;) (it's polish word play).

    http://en.wikipedia.org/wiki/Eratosthenes

    ReplyDelete