Update: I've tried, and the BitSet is fairly fast, but a simple boolean array seems better from my timings.

I note that some of the versions posted have some subtle bugs (and claim 169 and 301 as prime), but I'm fairly confident my solution is accurate.

I've avoided Wrapper classes, to avoid the boxing/unboxing costs, and used a boolean to mark a candidate number as known to be non-prime.

I thought that the numbering fell more comfortably without subtracting some offset, so made my array one entry larger than absolutely necessary.

import java.util.Arrays;

public class Sieve {

  private static final int NANOS_PER_SECOND = 1000_000_000;

  /*
   * [0] : ignored - allows us to do 1-based indexing cleanly
   * [n] : set if that integer is now known to be non-prime
   */
  private static boolean[] knownNonPrimes;

  private static int max;
  private static int maxFactor;

  public static void main(String[] args) {
    max = Integer.getInteger("Max", 10000);
    maxFactor = (int) Math.ceil(Math.sqrt(max)); // only need to check to root(max)
    knownNonPrimes = new boolean[max + 1]; // initially all false
    knownNonPrimes[0] = true; // zero is special
    markMultiples(2); // Special-case, to save checking other even numbers

    long startTime = System.nanoTime();
    int[] foundPrimes = findPrimes();
    long endTime = System.nanoTime();

    System.out.format("Time taken = %f seconds%n", 
      (double) (endTime - startTime) / NANOS_PER_SECOND);
    System.out.println(foundPrimes.length);
    System.out.println(Arrays.toString(foundPrimes));
  }

  private static int[] findPrimes() {
    for (int factor = 3; factor <= maxFactor; factor += 2) {
      // If we already know this is non-prime, 
      // then its multiples have been marked already
      if (!knownNonPrimes[factor]) {
        markMultiples(factor);
      }
    }

    int resultSize = 0;
    for (boolean knownNonPrime : knownNonPrimes) {
      if (!knownNonPrime) {
        resultSize += 1;
      }
    }
    int[] result = new int[resultSize];
    int resultIndex = 0;
    for (int primeCandidate = 1; primeCandidate <= max; primeCandidate++) {
      if (!knownNonPrimes[primeCandidate]) {
        result[resultIndex++] = primeCandidate;
      }
    }
    return result;
  }

  private static void markMultiples(int factor) {
    for (int multiple = factor * 2; multiple <= max; multiple += factor) {
      knownNonPrimes[multiple] = true;
    }
  }

}