Sieve of Eratosthenes

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 1 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:

Back to home