title: Improving a prime sieve algorithm
body: <p>I'm trying to make a decent Java program that generates the primes from 1 to N (mainly for Project Euler problems).</p>
  
  <p>At the moment, my algorithm is as follows:</p>
  
  <p>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.</p>
  
  <p>Set an integer, s equal to the lowest prime, (ie 2)</p>
  
  <p>While s is &lt;= sqrt(N)</p>
  
  <p>Set all multiples of s (starting at s^2) to true in the array/bitarray.</p>
  
  <p>Find the next smallest index in the array/bitarray which is false, use that as the new value of s.</p>
  
  <p>Endwhile.</p>
  
  <p>Go through the array/bitarray, and for every value that is false, put the corresponding index in the primes array.</p>
  
  <p>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 <a href="http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html" rel="nofollow noreferrer">here</a></p>
  
  <p>What can I do to improve?</p>
  
  <p>Edit: Okay, here's my actual code (for N of 1E7):</p>
  
  <pre><code>int l = 10000000, n = 2, sqrt = (int) Math.sqrt(l);
  boolean[] nums = new boolean[l + 1];
  int[] primes = new int[664579];
  
  while(n &lt;= sqrt){
      for(int i = 2 * n; i &lt;= l; nums[i] = true, i += n);
      for(n++; nums[n]; n++);
  }
  
  for(int i = 2, k = 0; i &lt; nums.length; i++) if(!nums[i]) primes[k++] = i;
  </code></pre>
  
  <p>Runs in about 350ms on my 2.0GHz machine.</p>