The Sieve of Eratosthenes is a fine example of the importance of a good algorithm and that it is much more important than CPU power

It's the following task: Compute all prime numbers between 2 and 1.000.000 and count them.

With a good algorithm it's computated in 9ms (see example) in Java. Just looping over the numbers and testing each of them for dividers needs days on any machine.

```
Time Elapsed: 9ms
There are 78498 Prime numbers between 2 and 1000000
```

This is the algorithm in Java:
```
int ROOT = 1000;
boolean NOPRIME[] = new boolean[ROOT*ROOT];
int countPrims = ROOT*ROOT - 2; // 0 and 1 are no primes
for (int i = 2; i < ROOT; i++) { // Therefore we start with 2
if (NOPRIME[i]) {
continue;
}
for (int x = i*i; x < ROOT*ROOT; x+=i) {
if (!NOPRIME[x]) {
NOPRIME[x] = true;
countPrims--;
}
}
}
```

SiebPanel.jar Executable Programm - SiebPanel.java Source Code in Java displaying all prime number. By a colleague: IntSieve.java using BitSet for even more efficiency.

And the black dots representing all prime numbes up to 1.000.000: