PrimeGap.java

/*************************************************************************
 *  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; }
      }

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