Eratosthenes Sieve algorithm for checking prime numbers.
Maybe we should first ask, what is prime number?
If one number can be calculated by multiplying any two different numbers then this number is not a prime number (We do not take number 1 into consideration). As example we can take few numbers 3,4,5,9,11.
Number 3 is prime as you can't multiple any other two numbers and get it.
Number 4 is not a prime number as you can get it by multiplying number 2 with 2 and get result as 4.
Number 5 is prime as well, while number 9 is not a prime, as you can get is as result 3*3.
Number 11 is prime as you can't get it as result of multiplying any other two numbers.
You can say, yes, it is easy, and sure it is for smaller numbers, but when you get into 3 digits or even 4 it is bit harder to calculate.
So how Eratosthenes sieve works.
Lets use number 117 for checking if it is prime number or not. Algorithm starts with simple numbers and multiply them until you get to number you want.
Starts with number 2 and start to calculate, 2*2, 2*3, 2*4, 2*5, 2*6, all results of this multiply will be marked as NOT PRIME in sieve as they are result of multiplying two numbers. We do multply and increasing numbers as long result is less then 117. Then we increase first number, now it is 3, 3*3, 3*4, 3*5, result or multiply are marked as NOT PRIME in sieve... Increasing first number to number 4? Nope, it doesn't use number 4 as it is not prime, and sieve knows it, because we marked it as not prime when we calculated 2*2. Next number will be 5, so 5*2, 5*3, 5*4... and so on, until we reach first number as number 117. At this point, all numbers in seive are marked as NOT PRIME, we should now just checked the sieve and see if our number is prime or not.
Have a look at code below. Algorithm will use same approach and print out if number is prime or not, with limit that user enters.
import java.io.*;
public class EratosthensSievePrimeNumbers {
// Start of the program
public static void main(String args[]) throws IOException {
boolean[] sieve; // array to keep track if number is prime or not
//value for each number will be true or false
int index; // index used in for loops
int jIndex; // jIndex second index used in for loops
int limit; // limit for sieve, provided by user
// used to read input from user
BufferedReader readUserInput = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter limit for prime number search: ");
limit = Integer.parseInt(readUserInput.readLine());
sieve = new boolean[limit]; // first: allocate memory
for (index = 2; index < limit; index++) {
sieve[index] = true; // setting all numbers as potential prime numbers
}
for (index = 2; index < limit; index++){
if (sieve[index]) {
for (jIndex = index + index; jIndex < limit; jIndex += index)
// exclude all numbers that we are multiplying by index from the list
sieve[jIndex] = false;
} // 2 * i, 3 * i ...
}
// Going over list and printing out all prime numbers that still have true as value.
for (index = 2; index < limit; index++){
if (sieve[index]){
System.out.println("Prime number is: " + index);
}
}
}
}
I hope this will be helpful for anyone interested to see how Eratosthenes Sieve works, if you still have any doubts, add a comment with your question and I will try to answer it.
