/******************************************************************************
 *  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 factor = 2; factor*factor <= n; factor++) {
            if (isprime[factor]) {
                for (int j = factor; factor*j <= n; j++)
                    isprime[factor*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");
    }
}