Sieve of Eratosthenes in Java / C#

Eratosthenes, what an egg head huh? I wonder if he could have coded his own algorithm in Java or C#. Would he have known what a class, helper method, and a delegate is? The ancient Greeks had the math world pretty much locked up for their time… except that whole world at the center of the universe thing and that the heavens were in perfectly circular orbits. Whoa were they wrong on that one huh! But as far as the whole math deal went, it was their favorite topic at the mineral baths…. so why not cover a few examples of this ancient math algorithm here on this entry of the Programming Underground!

Eratosthenes was famous for his killer water polo, whipping others with a wet towel, but most of all his algorithm for finding prime numbers. The whole process begins by constructing a list of numbers from 2 to some higher number. Then by crossing off multiples you are left with the prime numbers… those numbers without any factors.

So for instance, lets say we wanted to find the prime numbers up to 120. We would start with 2, our first prime number, and then start crossing all multiples of 2. We cross off 4, 6, 8, 10, 12…. all the way up to 120. The first number left over from that is 3. Next we cross off all multiples of 3….6, 9, 12, 15… all the way up to 120. You keep doing this until the counter squared is larger than our maximum number (our value 120).

Sound pretty easy? It is, the only thing you have to make sure you get right is the numbering in the array. Lets take a look at this algorithm in Java…

import java.util.Scanner;

public class sieve {
	public static void main(String args[]) {
		// Collect input from the user
		Scanner userInput = new Scanner(System.in);
		System.out.print("Enter a maximum integer: ");
		int num = userInput.nextInt();

		// Setup an array of the size specified
		int[] numbers = new int[num + 1];

		// Starting at 2, initialize the array up to the number specified.
		int count = 2;
		for (int i = 2; i <= num; i++) {
			numbers[i] = count;
			count++;
		}

		// Now starting at two and going until the square of the counter is less 
		// than the number specified, start crossing out multiples with a zero.

		for(int i = 2; (i * i) <= num; i++ ){
			for (int j = (i * i); j <= num; j = j + i) {
				numbers[j] = 0;
			}
		}

		// Now go back through the array and look for the values not crossed out.
		// Those will be your prime numbers.

		for (int i = 2; i <= num; i++) {
			if (numbers[i] != 0) { System.out.println("Prime: " + numbers[i]); }
		}

	}
}

The first thing we do is setup an array and initialize it from element 2 onwards. We add one onto the size in the event that the number they type is a prime itself, we have to then test that number. Second, we again start at 2 and square it, this will mark our starting point for multiples. We can start at the square because all numbers before that have been crossed off. We start our counter at 2 and start crossing numbers off at 2^2 = 4. Next time around when our counter is 3, we start crossing off from 3^3 = 9 (6 would have already been crossed off by the multiples of 2). Hopefully that makes sense.

Lastly, once the square of our counter is greater than maximum number we specified, we know we have gone through all the multiples. The numbers that are not crossed off are then our primes. We then list these numbers at the end.

This program is fairly easy to convert to something like C++ or C#. I have included an example of the code above ported over to C# using a textbox to collect the number, a listbox to show it, and a button to trigger the finding of primes.

namespace sieve {
	public partial class Form1 : Form {
		public Form1()
		{
			InitializeComponent();
		}

		private void btnPrimes_Click(object sender, EventArgs e)
		{
			int result;
			Int32.TryParse(txtMaxNumber.Text, out result);

			if (result > 0) {
				findPrimes(result);
			}
		}

		private void findPrimes(int size)
		{
			// Setup an array of the size specified
			int[] numbers = new int[size + 1];

			// Starting at 2, initialize the array up to the number specified.
			int count = 2;
			for (int i = 2; i <= size; i++) {
				numbers[i] = count;
				count++;
			}

			// Now starting at two and going until the square of the counter is less 
			// than the number specified, start crossing out multiples with a zero.

			for (int i = 2; (i * i) <= size; i++) {
				for (int j = (i * i); j <= size; j = j + i) {
					numbers[j] = 0;
				}
			}

			// Now go back through the array and look for the values not crossed out.
			// Those will be your prime numbers.
			lstPrimes.Items.Clear();

			for (int i = 2; i <= size; i++) {
						if (numbers[i] != 0) { lstPrimes.Items.Add(numbers[i]); }
			}
		}
	}
}

Not too bad eh? Feel free to modify these examples as you see fit and dazzle your friends with your elite programming skills. I am sure Eratosthenes would have wanted it that way. Being an egghead he probably didn’t have friends of his own and now he can share yours.

I hope these examples prove useful to you. Enjoy! 🙂