#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.

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++) {
}
}

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