Generating a List of Primes: The Sieve of Eratosthenes

Learned of The Sieve of Eratosthenes from Cracking the Coding Interview Ed. 5.

The Sieve of Eratosthenes is a highly efficient way to generate a list of primes. It works by recognizing that all non-prime numbers are divisible by a prime number.

Algorithm: Start with a list of all numbers up through a value, Max.  Cross off all multiples of prime numbers (2,3,4,7….) and end up with a list of prime numbers from 2 through Max.

In the book, it gives an explanation and code. It suggests one simple optimization which is to use only use odd numbers in the array, which would reduce space usage by half.  I implemented the simple optimization of using only odd numbers. Not too bad, a little tricky but doable. I think it’d be a pretty good interview question. It can be done within a short amount of time and simple enough.

boolean[] sieveOfEratosthenesOdd(int max) {
		boolean[] bArr;

		if (max%2 == 1)
			bArr = new boolean[max/2+1]; // Max is odd
		else
			bArr = new boolean[max/2]; // Max is even

		bArr[0] = true; // bArr[0] represent 2
		for (int i = 1; i < bArr.length; i++) {
			bArr[i] = true;
		}
		int prime = 3;

		while (prime <= max) {
			crossOffOdd(bArr, prime);
			prime = nextPrimeOdd(bArr, prime);
		}

		return bArr;
	}
	void crossOffOdd(boolean arr[], int num) {
		// Odd * even is even. So need to find ever other multiple
		int n = num*3;
		// (arr.length*2-1) = MAX odd number
		while(n <= (arr.length*2-1)) {
			arr[n/2] = false;
			n+=(2*num);
		}			
	}
	int nextPrimeOdd(boolean arr[], int prime) {
		// next is a index into the array so need conversion
		int next = prime/2+1;
		while (next < arr.length && !arr[next]) {
			next++;
		}
		// convert next back into a number
		return next*2+1;
	}
Advertisements
This entry was posted in Coding. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s