## 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 = true; // bArr 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;
}```
This entry was posted in Coding. Bookmark the permalink.