I'm trying to make a decent Java program that generates the primes from 1 to N (mainly for Project Euler problems).

At the moment, my algorithm is as follows:

Initialise an array of booleans (or a bitarray if N is sufficiently large) so they're all false, and an array of ints to store the primes found.

Set an integer, s equal to the lowest prime, (ie 2)

While s is <= sqrt(N)

Set all multiples of s (starting at s^2) to true in the array/bitarray.

Find the next smallest index in the array/bitarray which is false, use that as the new value of s.

Endwhile.

Go through the array/bitarray, and for every value that is false, put the corresponding index in the primes array.

Now, I've tried skipping over numbers not of the form 6k + 1 or 6k + 5, but that only gives me a ~2x speed up, whilst I've seen programs run orders of magnitudes faster than mine (albeit with very convoluted code), such as the one here

What can I do to improve?

Edit: Okay, here's my actual code (for N of 1E7):

```
int l = 10000000, n = 2, sqrt = (int) Math.sqrt(l);
boolean[] nums = new boolean[l + 1];
int[] primes = new int[664579];
while(n <= sqrt){
for(int i = 2 * n; i <= l; nums[i] = true, i += n);
for(n++; nums[n]; n++);
}
for(int i = 2, k = 0; i < nums.length; i++) if(!nums[i]) primes[k++] = i;
```

Runs in about 350ms on my 2.0GHz machine.