/** Solve a common student exercise - display the primes
from 2 up to a specified limit. */
public class Example{
  public static void main(String[] args){
    //Find and print primes up to args[0].

    //Convert and validate the command line argument
    if(args.length < 1){
      System.err.println("Usage: java Example max");
      System.exit(3);
    }
    int max=0;
    try{
      max = Integer.parseInt(args[0]);
    }catch(NumberFormatException e){
      e.printStackTrace();
      System.exit(2);
    }
    if(max < 2){
      System.err.println(
          "Maximum prime to look for must be 2 or greater");
      System.exit(1);
    }

    // Get the required primes in an array
    PrimeFinder pf = new PrimeFinder();
    int[] primes = pf.getPrimes(max);

    // Print them.
    for(int i=0;i<primes.length;i++){
      System.out.println(primes[i]);
    }
  }
}

/** Prime number finder. */
class PrimeFinder{

  /** Get the primes.
  @return An array containing the primes from 2 through the
  largest prime less than or equal to max.
  @param max The upper bound of the range to search for
  primes. */
  int[] getPrimes(int max){
    /* Use sieve method to eliminate all numbers
    that are divisible by 2 through sqrt(count). */

    /* Sieve set - all composite numbers in the range 2
    through max will be represented in this set. */
    FixedSizedBitSet sieve = new FixedSizedBitSet(max+1);

    /* The primes, will contain the values in the range 2
    through max that have not been found to be composite. */
    FixedSizedBitSet results = new FixedSizedBitSet(max+1);

    /* All composite numbers less than or equal to max
    will have at least one factor less than or equal to
    stop. */
    int stop = (int)Math.sqrt(max);

    /* First do the sieving - add all composite numbers
    in the range to sieve set. */
    for(int i=2;i<stop;i++){
      if(!sieve.contains(i)){
        for(int j=2*i;j<=max;j+=i){
          sieve.add(j);
        }
      }
    }

    /* Now find the numbers in the range that are not in
    the sieve set. */
    for(int i=2;i<=max;i++){
      if(!sieve.contains(i)){
        results.add(i);
      }
    }
    return results.toIntArray();
  }
}

/** Simple bit set for pre-determined sizes. */
class FixedSizedBitSet{
  long[] bits;
  int elems;  // number of potential elements

  /** Create a set based on a specified number of
  potential elements.
  The elements will be indexed 0 through elems-1.
  @param elems Number of potential elements */
  FixedSizedBitSet(int elems){
    this.elems = elems;
    bits = new long[(elems+63)/64];
  }

  /** Add a specified element to the set
  @param elem Element number to add */
  void add(int elem) throws IllegalArgumentException{
    if(elem >= elems || elem < 0){
      throw new IllegalArgumentException();
    }
    bits[elem/64] |= mask(elem);
  }

  /** Remove a specified element from the set
  @param elem Element number to remove */
  void remove(int elem)throws IllegalArgumentException{
    if(elem >= elems || elem < 0){
      throw new IllegalArgumentException();
    }
    bits[elem/64] &= ~mask(elem);
  }

  /** Test whether a specified element is in the set.
  @param elem The element to set
  @return true if it is present, false if it is absent */
  boolean contains(int elem){
    boolean result=false;
    if(elem < 0 || elem >= elems){
      return false;
    }
    return (bits[elem/64] & mask(elem))!=0;
  }

  /** Construct a mask with only the bit corresponding
  to the element number on.
  @param elem The element number */
  private long mask(int elem){
    return 1 << (elem %64);
  }

  /** Return int[] representation.
  @return An int[] containing the element numbers that
  are currently in this set, in ascending order */
  int[] toIntArray(){
    // Count the elements in the set.
    int count=0;
    for(int i=0;i<elems;i++){
      if(contains(i)){
        count++;
      }
    }

    // Create an array to contain that number of elements
    int[] results = new int[count];

    // Fill in the ones that are in the set.
    int j = 0;
    for(int i=0;i<elems;i++){
      if(contains(i)){
        results[j] = i;
        j++;
      }
    }
    return results;
  }
}