public class GoFarIterSieve {
	
	final int chunk = 100000000;

	int oddBalance = 0;
	IntegerStack primes = new IntegerStack();
	
	int offset = 2;
	
	boolean[] isPrime = new boolean[chunk];
	boolean[] oddTypes = new boolean[chunk];
	
	int limit;
	
	public GoFarIterSieve() {
		for(int i=0; i<chunk; i++) {
			isPrime[i] = true;
			oddTypes[i] = false;
		}

		IntegerStack.Iterator primeWalk;
		while(true) {
			limit = offset + chunk;
			primeWalk = primes.iterator();
			while(primeWalk.hasNext()) {
				int p = primeWalk.next();
				
				int lowMult = offset / p;
				if(lowMult * p < offset) {
					lowMult += 1;
				}
				applyPrime(p, lowMult);
			}
			runSieve();
			System.out.println("Checkpoint: "+(limit-1)+": "+oddBalance);
			offset += chunk;
		}
	}
	
	private void applyPrime(int p, int lowMult) {
		int highMult = (limit-1)/p;
		// iterate up the multipliers of p
		for(int mult = lowMult; mult <= highMult; mult++) {
			int product = mult * p;
			isPrime[product-offset] = false;
			
			// check for an odd number of repeated factors of p in the product
			int residual = mult; // product/p
			boolean oddRepeats = true; // 1+?
			while(residual % p == 0) { // do this check instead of waiting for residual to become a fraction... because a power of n will reduce to 1
				oddRepeats = !oddRepeats;
				residual /= p;
			}
			if(oddRepeats) {
				oddTypes[product-offset] = !oddTypes[product-offset];
			}
 		}
	}
	
	private void runSieve() {
		for(int n=offset; n < limit; n++) {
			int nDex = n-offset;
			if(isPrime[nDex]) {
				primes.add(n);
				oddTypes[nDex] = true;
				
				applyPrime(n, 2);
			}
			
			oddBalance += (oddTypes[nDex] ? +1 : -1);
			
//			System.out.println(n+": "+oddBalance);
			if(oddBalance < 0) {
				System.out.println("Success! "+n+": "+oddBalance);
				System.exit(0);
			}
			
			//reset for next round
			oddTypes[nDex] = false;
			isPrime[nDex] = true;
		}
	}

	public static void main(String[] args) {
		new GoFarIterSieve();
	}
}