import java.util.ArrayList;
import java.util.Collections;

import java.util.PriorityQueue;
import java.util.Comparator;

public class Main {
	public static void main(String[] args) {
		Sieve sieve = new Sieve();
		ArrayList<Integer> primes = new ArrayList<Integer>();
		
		while (primes.size() < 31) {
			primes.add(sieve.nextPrime());
		}
		
		System.out.println("\nPrimes after 31:");
		System.out.println(primes);
		
		System.out.println("\nSieve heap after 31:");
		System.out.println(sieve.queue);
		
		ArrayList<Sieve.PrimeCounter> sieveState = new ArrayList<Sieve.PrimeCounter>(sieve.queue);
		Collections.sort(sieveState, sieve.queue.comparator());
		
		System.out.println("\nOrdered sieve state after 31:");
		System.out.println(sieveState);
		
		
		while (primes.size() < 35) {
			primes.add(sieve.nextPrime());
		}
		System.out.println("\nPrimes:");
		System.out.println(primes);
	}
	
	public static class Sieve {
		public PriorityQueue<PrimeCounter> queue;
		public Integer current = 2;
		
		Sieve() {
			Comparator<PrimeCounter> c = new Comparator<PrimeCounter>() {
				public int compare(PrimeCounter a, PrimeCounter b) {
					return a.multiple.compareTo(b.multiple);
				}
			};
			queue = new PriorityQueue<PrimeCounter>(1000, c);
		}
		
		public Integer nextPrime() {
			// Determine the prime
			
			// If we're not at the first prime.
			if (!queue.isEmpty()) {
				PrimeCounter top;
				// Infinite loop with break.
				while (true) {
					top = queue.peek();
					// The top primecounter needs to be updated.
					if (top.multiple < current) {
						top = queue.poll();
						top.nextMultiple();
						queue.add(top);
					}
					// The current number isn't a prime; go on to the next one.
					else if (top.multiple == current) {
						current++;
					}
					// We've found a prime.
					else {
						break;
					}
				}
			}
			
			// Handle bookkeeping.
			Integer prime = current;
			current++;
			queue.add(new PrimeCounter(prime));
			
			// Return the prime.
			return prime;
		}
		
		public static class PrimeCounter {
			public Integer prime;
			public Integer multiple;
			
			PrimeCounter(Integer prime) {
				this.prime = prime;
				this.multiple = prime;
			}
			
			public void nextMultiple() {
				multiple += prime;
			}
			
			public String toString() {
				return "[" + prime + ":" + multiple + "]";
			}
		}
	}
}