import java.util.ArrayList;
// Find primes up to 1 million
// Only check for prime factors

public class Test {

  // primes is prime numbers found so far
  // construct with large initial capacity
  static ArrayList<Long> primes = new ArrayList<>(65536);

  public static void main(String[] args) {
    primes.add(2L);primes.add(3L); // start with first 2 primes
    for (long i = 5; i<1000000; i += 2) { // is i a prime?
      // just odd numbers after 3

      int n = 1; // index into primes for possible divisor
      long div = primes.get(n); // get possible divisor
      long limit = (long) Math.sqrt(i); // only try up to square root of i
      //System.out.println("Limit = "+limit);
      boolean foundDiv = false; // have we found a divisor yet?
      while (div <= limit && !foundDiv) {
        //System.out.println("Checking div by "+div);
        if (i % div == 0) { // found a divisor
          foundDiv = true;
          continue;
        }
        n++; // go on to next possible divisor
        div = primes.get(n);
      }
      if (!foundDiv) { // add it to list of primes
        primes.add(i);
        System.out.println(i+" is prime");
      }
    }

  }

}