PrimeGap.java

Below is the syntax highlighted version of PrimeGap.java from §1.4 Arrays.

/*************************************************************************
 *  Compilation:  javac PrimeGap.java
 *  Execution:    java -Xmx900MB -Xms900MB PrimeGap N
 *  
 *  Find the longest consecutive sequence of integers between 2 and N
 *  with no primes.
 *
 *  Sample execution:
 *
 *     % java -Xmx900MB -Xms900MB PrimeGap 100
 *     There are no primes between 90 and 96
 *     That is 7 consecutive integers
 *
 *     % java -Xmx900MB -Xms900MB PrimeGap 100000000
 *     There are no primes between 47326694 and 47326912
 *     That is 219 consecutive integers
 *
 *
 *************************************************************************/


public class PrimeGap {
    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);

         boolean[] isprime = new boolean[N+1];

         for (int i = 2; i <= N; i++)
             isprime[i] = true;

         // determine primes < N using Sieve of Eratosthenes
         for (int i = 2; i*i <= N; i++) {
             if (isprime[i]) {
                 for (int j = i; i*j <= N; j++)
                     isprime[i*j] = false;
             }
         }

         // find longest consecutive sequence of integers with no primes
         int gap = 0;
         int bestgap = 0;
         int right = 0;
         for (int i = 2; i <= N; i++) {
             if (isprime[i]) gap = 0;
             else gap++;
             if (gap > bestgap) { bestgap = gap; right = i; }
         }

         int left = right - bestgap + 1;
         System.out.println("There are no primes between " + left + " and " + right);
         System.out.println("That is " + bestgap + " consecutive integers");
    }
}