import java.util.*;
public class primes {

	/**
	 * Prints an array filled with prime numbers (or any int).
	 * Uses the java 5 style "for (type name : array)" for loop.
	 * 
	 * @param primes An int array of any length computable.
	 */
	public static void printPrimes (LinkedList<Integer> primes) {
		System.out.print("The first " + primes.size() + " primes are:");
		for (int prime : primes) {
			System.out.print(" " + prime + " ");
		}
		System.out.println();
	}
	
	/**
	 * Computes <quantity> prime numbers into an array.
	 * Uses extendPrimes if array.length < quantity.
	 * 
	 * @param quantity Natural number of prime numbers to compute.
	 * @return An array containing <quantity> prime numbers.
	 */
	public static LinkedList<Integer> findPrimes (int quantity){
		LinkedList<Integer> primes = new LinkedList<Integer>();
		
		// set first prime number
		primes = extendPrimes (primes, quantity);
		return primes;
	}
                                                                               
	/**
	 * Computes targetNumber prime numbers. Extends the given array primes if needed by
	 * creating a new array with targetNumber size and copying the already given prime Numbers.
	 * 
	 * @param primes An int array filled with prime numbers (or to be extended and filled).
	 * @param targetNumber Number of primes that should be in the array that is returned.
	 * @return Array of length targetNumber filled with primes
	 */
	private static LinkedList<Integer> extendPrimes (LinkedList <Integer> primes, int targetNumber) {
		int NumberFound = 2;
		// set the first two prime numbers
		if (primes.size() < 2) {
			if (targetNumber >= 1) primes.add(2);
			if (targetNumber >= 2) primes.add(3);
		}
		// candidate for testing
		int candidate = primes.getLast() + 2;
		boolean isprime = true;
		while (NumberFound < targetNumber) {
			isprime = true;
			for (int knownp : primes) {
				if (candidate % knownp == 0) {
					isprime = false;
					break;
				}
			}
			if (isprime) {
				primes.add(candidate);
				NumberFound++;
			}
			candidate = candidate + 2;
		}
		return primes;
	}
	
	/**
	 * Prints <number> pairs of prime numbers which follow the following
	 * condition: abs(p - p') == 2. Begin with the smallest.
	 * 
	 * @param primes
	 *           An int array filled with prime numbers.
	 * @param number
	 *           Natural number of primeTwins to be found and printed.
	 */
	public static void printPrimeTwins (LinkedList<Integer> primes, int number) {
		System.out.print("The first " + number + " Primetwins are:");
		int foundNumber = 0;
		int i = 0;
		int tmpPrime1;
		int tmpPrime2 = 2;
		while (foundNumber < number) {
			if (i + 1 >= primes.size()) {
				primes = extendPrimes(primes, number + 2);
			}
			tmpPrime1 = tmpPrime2;
			tmpPrime2 = primes.get(i + 1);
			if (Math.abs(tmpPrime1 - tmpPrime2) == 2) {
				System.out.print(" (" + tmpPrime1 + "," + tmpPrime2 + ") ");
				foundNumber++;
			}

			i++;
		}
		System.out.println();
	}
	
	/**
	 * Find smallest prime number whose successor is at least <delta> bigger.
	 * 
	 * @param primes An int array filled with prime numbers.
	 * @param delta Difference between the two prime numbers.
	 * @return prime number p where nextp - p > delta
	 */
	public static void printDeltaPrime (LinkedList<Integer> primes, int delta) {
		int i = 2;
		int tmpPrime1 = 2;
		int tmpPrime2 = 3;
		
		System.out.println("Searching for succeding primes with delta > " + delta);

		while ((tmpPrime2 - tmpPrime1) <= delta) {
			if (i >= primes.size() - 1) {
				extendPrimes(primes, delta + 2);
			}
			
			tmpPrime1 = tmpPrime2;
			tmpPrime2 = primes.get(i);
			
			if (i % 10000 == 0) {
				System.out.println ("    testing prime numbers > " + i +"...");
			}
			i++;
		}			
		System.out.println("  Computed " + primes.size() + " prime numbers");
		System.out.println("  Lowest prime and it's succeeding prime are " + 
							tmpPrime1 + " and " + tmpPrime2 +", ");
		System.out.println("  delta is " + (tmpPrime2 - tmpPrime1));
	}

	/**
	 * Used to let the class be a program and run.
	 * 
	 * @param args If we wanted to pass arguments to main, we would need this.
	 */
	public static void main(String[] args) {
		final int primesQuantity = 20;
		final int primeTwinsQuantity = 50;
		final int primeDelta = 50;
		LinkedList<Integer> primes = new LinkedList<Integer>();
		primes = findPrimes (primesQuantity);
		printPrimes (primes); 
		System.out.println("");
		printPrimeTwins (primes, primeTwinsQuantity);
		System.out.println("");
		printDeltaPrime (primes, primeDelta);
	}
}