Difference between the largest and the smallest primes in an array in Java

Problem Statement

With a given array of integers where all elements are less than 1000000. Find the difference between the largest and the smallest primes in an array.

Example

Array: [ 1, 2, 3, 4, 5 ] Largest Prime Number = 5 Smallest Prime Number = 2 Difference = 5 - 3 = 2.

Solution

Use Sieve of Eratosthenes approach, which is an efficient way to find out all prime numbers smaller than a given number. Then we will figure out the largest and smallest prime number to get the required difference.

Example

 Live Demo

Following is the program in Java to find the required output.

public class JavaTester {    static int MAX = 1000000;    static boolean prime[] = new boolean[MAX + 1];    public static void runSieveOfEratosthenes(){       //reset prime flags to be true       for(int i=0; i< MAX+1; i++) prime[i] = true;       //set 1 as non-prime       prime[1] = false;       for (int p = 2; p * p <= MAX; p++) {          // If prime[p] is not modified, then it is a prime          if (prime[p]) {             // Update all multiples of p             for (int i = p * 2; i <= MAX; i += p) prime[i] = false;          }       }    }    public static int difference(int arr[]){       int min = MAX + 2;       int max = -1;       for (int i = 0; i < arr.length; i++) {          // check if the number is prime or not          if (prime[arr[i]] == true) {             // set the max and min values             if (arr[i] > max) max = arr[i];             if (arr[i] < min) min = arr[i];          }       }       return max - min;    }    public static void main(String args[]){       // run the sieve       runSieveOfEratosthenes();       int arr[] = { 1, 2, 3, 4, 5 };       System.out.println(difference(arr));    } }

Output

3