Your implementation is really strange however it seems to come up with good results. I was interested in your claim about the computation time being a third of Sieve of Eratosthenes.

After testing against this claim (and i did it properly: had a loop before either of the methods executed to get the JVM warmed up) here are my personal results:

1. Your method: 97779ns
2. Sieve of Eratosthenes: 98933ns

This was running against 1000 integers.

Note: I did not include time for printing out the integers as Console writing is slow and unnecessary in terms of calculating the values.

int N = maxNumber; //from the earlier sieve implementation

// initially assume all integers are prime
boolean[] isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++) {
    isPrime[i] = true;
}

// mark non-primes <= N using Sieve of Eratosthenes
for (int i = 2; i*i <= N; i++) {

    // if i is prime, then mark multiples of i as nonprime
    // suffices to consider multiples i, i+1, ..., N/i
    if (isPrime[i]) {
        for (int j = i; i*j <= N; j++) {
            isPrime[i*j] = false;
        }
    }
}

This was the Sieve code that I used (not my own).

I wouldn't say that it's much faster in this particular instance and that makes sense especially since it seems that you merely optimized the original sieve. I would say that the time complexity would match that of the original sieve; however, time complexities like this are hard to compute especially since it relies on a property of numbers that, at the moment, we don't have a clean way of calculating the behaviour over a set interval.

Your implementation is really strange however it seems to come up with good results. I was interested in your claim about the computation time being a third of Sieve of Eratosthenes.

After testing against this claim (and i did it properly: had a loop before either of the methods executed to get the JVM warmed up) here are my personal results:

1. Your method: 97779ns
2. Sieve of Eratosthenes: 98933ns

This was running against 1000 integers.

Note: I did not include time for printing out the integers as Console writing is slow and unnecessary in terms of calculating the values.

int N = maxNumber; //from the earlier sieve implementation

// initially assume all integers are prime
boolean[] isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++) {
    isPrime[i] = true;
}

// mark non-primes <= N using Sieve of Eratosthenes
for (int i = 2; i*i <= N; i++) {

    // if i is prime, then mark multiples of i as nonprime
    // suffices to consider multiples i, i+1, ..., N/i
    if (isPrime[i]) {
        for (int j = i; i*j <= N; j++) {
            isPrime[i*j] = false;
        }
    }
}

This was the Sieve code that I used (not my own).

I wouldn't say that it's much faster in this particular instance and that makes sense especially since it seems that you merely optimized the original sieve. I would say that the time complexity would match that of the original sieve; however, time complexities like this are hard to compute especially since it relies on a property of numbers that, at the moment, we don't have a clean way of calculating the behaviour over a set interval.

One value for the time complexity (assuming that your implementation closely models or only optimizes a little the computation time) would be O(n log(log(n))) since the prime harmonics approach log(log(n)). (Sieve of Erathosthenes)

I would guess that at worst case, your algorithm approaches the aforementioned value.