Eratosthenes Sieve - Prime numbers in Java - Algorithm Example

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.

Best algorithms for sorting arrays - Java

Bubble sort, Insertion sort and Selection sort

Which one you will use depends on what do you need. Bubble sort is a simplest algorithm, it will do the job but he will be slow, if you need something faster try Selection Sort and Insertion Sort.

They use different methods of sorting if you want to know how they works read it on this links:

Insertion Sort

Selection Sort

Bubble Sort

My example of implementation this 3 algorithm's, I add speed test so you will see results which one is the best.

Notice: If you are using algorithms for different things, test it in all 3 algorithms it can give different results.

public class Example {

    public static void insertion_sort (int array[]) {
        long start = System.nanoTime();
        for (int i = 1; i < array.length; i++) {
            int j = i;
            int B = array[i];
            while ((j > 0) && (array[j-1] > B)) {
                array[j] = array[j-1];
                j--;
            }
            array[j] = B;
        }
        long total = System.nanoTime() - start;
        System.out.println("Time needed for sorting: "
                + (total / 1000000.0));
    }

    public static void selection_sort (int array[]) {
        long start = System.nanoTime();
        for (int x = 0; x < array.length; x++) {
            int index_of_min = x;
            for (int y = x; y < array.length; y++) {
                if (array[index_of_min] < array[y]) {
                    index_of_min = y;
                }
            }
            int temp = array[x];
            array[x] = array[index_of_min];
            array[index_of_min] = temp;
        }
        long total = System.nanoTime() - start;
        System.out.println("Time needed for sorting: "
                + (total / 1000000.0));
    }


    public static void bubble_sort( int a[] ) {
        long start = System.nanoTime();
        int i, j,t=0;
        for (i = 0; i < a.length; i++) {
            for (j = 1; j < (a.length-i); j++) {
                if (a[j-1] > a[j]){
                    t = a[j-1];
                    a[j-1] = a[j];
                    a[j] = t;
                }
            }
        }
        long total = System.nanoTime() - start;
        System.out.println("Time needed for sorting: "
                + (total / 1000000.0));
    }
   
   
    public static void main (String [] args) {
        int i;
        int array[] = {12,9,3,5,7,9,11,17,22,15,4,99,120,1,3,10};
        System.out.println();
        bubble_sort(array);
        System.out.print("After bubble sort algorithm:\n");
        for(i = 0; i <array.length; i++)
        System.out.print(array[i]+"  ");
        System.out.println();
       
        int p;
        int array2[] = {12,9,3,5,7,9,11,17,22,15,4,99,120,1,3,10};
        System.out.println();
        selection_sort(array2);
        System.out.print("After selection sort algorithm:\n");
        for(p = 0; p < array2.length; p++)
        System.out.print(array2[p]+"  ");
        System.out.println();
       
        int c;
        int array3[] = {12,9,3,5,7,9,11,17,22,15,4,99,120,1,3,10};
        System.out.println();
        insertion_sort(array3);
        System.out.print("After insertion sort algorithm:\n");
        for(c = 0; c < array3.length; c++)
        System.out.print(array3[c]+"  ");
        System.out.println();

    }
}

If you see this as useful please subscribe, like it, share it do whatever you want with it.
Have a good one. M.L.