title: Sieve of Eratosthenes in Java: A Puzzle and some optimization
body: <p>I did a quick implementation of the SoE algo in Java (code at the end). The output on my dual core AMD processor is:</p>
  
  <pre>
  Allocation:      31
  Meat:            10140
  Listing:         10171
  Preparing end:   10187
  </pre>
  
  <ul>
  <li><p>The "Meat" section consumes the Maximum amount of time, as expected.</p></li>
  <li><p>One observation I had was that using <code>Math.pow(variable, 2)</code> is slower than <code>(variable * variable)</code>. I think other than the function jump, there might be other overheads.</p></li>
  <li><p>Does Math.pow(x, 2) have optimizations for powers of 2, 3 etc? I ask because there are some user contributed Java libraries out there with much faster multiplication algos than Java's native ones.</p></li>
  </ul>
  
  <p>Here are my questions:</p>
  
  <ul>
  <li><p>What arithmetic optimizations can you suggest to the Meat section? Is there any way I can avoid the modulus operator altogether?</p></li>
  <li><p><strong>The function does not work when start == end. If I do sieve(4, 4), the returned array is of length 1: [4]. What am I doing wrong? It should return [] (basically new int(0)).</strong></p></li>
  <li><p>What are some of the fast number/maths related Java libraries you know?</p></li>
  </ul>
  
  <p>Thanks for reading. Finally Here's the code I wrote: Not GangOfFour/TopCoder quality, but not too pathetic either (I hope!, and code formatting at SO is sort of....weird?):</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.Iterator;
  import java.util.List;
  public class Sieve {
  
      public static void main(String[] args) {
  
          /* small test */
          int[] primes = sieve(1, 1000000);
      }
  
      /**
       * returns an array of prime integers
       * in the given range
       * 
       * @param start     range start
       * @param end       range end
       * @return
       */
      private static int[] sieve(int start, int end) {
  
          long startTime = System.currentTimeMillis();
  
          /* some basic range checks */
          if(end &lt; start || start &lt; 1 || end  &lt; 1) {
              throw new ArithmeticException("Messed up input");
          }
  
          /* generate ints within range */
          int[] naturals = new int[end-start+1];
          for (int j = 0; j &lt; end - start + 1; j++) {
              naturals[j] = start + j;
          }
          System.out.println("Allocation: \t" + (System.currentTimeMillis() - startTime));
  
          /* init running prime to start, and increment until
           * running prime squared is greater than the end
           */
          for (int runningPrime = (start == 1 ? 2: start); end &gt; runningPrime*runningPrime; runningPrime++) {
              for (int i = runningPrime; i &lt; naturals.length; i++) {
                  if(-1 != naturals[i]) {
                      if(naturals[i] % runningPrime == 0) {
                          naturals[i] = -1;
                      }
                  }
              }
          }
          System.out.println("Meat: \t\t" + (System.currentTimeMillis() - startTime));
  
          if(naturals[0] == 1) {
              naturals[0] = -1;
          }
  
          /* list primes */
          List list = new ArrayList();
          for (int i = 0; i &lt; naturals.length; i++) {
              if(-1 != naturals[i])
                  list.add(naturals[i]);
          }
          System.out.println("Listing: \t" + (System.currentTimeMillis() - startTime));
  
          /* create the return int array */
          int[] primes = new int[list.size()];
          int k = 0;
          for (Iterator iterator = list.iterator(); iterator.hasNext();) {
              primes[k++] = ((Integer) iterator.next()).intValue();
          }
  
          System.out.println("Preparing end: \t" + (System.currentTimeMillis() - startTime));
          return primes;
      }
  }
  </code></pre>
  
  <p>Thanks for all the feedback. This is the fixed version below (until someone manages to break it again :)</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.Iterator;
  import java.util.List;
  
  public class Sieve {
      public static void main(String[] args) {
          /* small test */
          int[] primes = sieve(2, 5);
          System.out.println("Number of primes: " + primes.length);
          for (int i : primes) {
              System.out.println(i);
          }
      }
  
  /**
   * returns an array of prime integers
   * in the given range
   * 
   * @param start     range start
   * @param end       range end
   * @return
   */
  private static int[] sieve(int start, int end) {
  
      long startTime = System.currentTimeMillis();
  
      /* some basic range checks */
      if(end &lt; start || start &lt; 1 || end  &lt; 1) {
          throw new ArithmeticException("Messed up input");
      }
  
      /* generate ints within range */
      int[] naturals = new int[(int)Math.floor((end-start+1) / 2) + 1];
      int allocator = 0;
      for (int j = 0; j &lt; end - start + 1; j++) {
          if(!((start + j) % 2 == 0)) {
              naturals[allocator++] = start + j;
          }
      }
      System.out.println("Allocation: \t" + (System.currentTimeMillis() - startTime));
  
      /* init running prime to 2, and increment until
       * running prime squared is greater than the end
       */
      for (int runningPrime = 2; end &gt;= runningPrime*runningPrime; runningPrime++) {
          for (int i = 0; i &lt; naturals.length; i++) {
              if(-1 != naturals[i]) {
                  if(naturals[i] != runningPrime &amp;&amp; naturals[i] % runningPrime == 0) {
                      naturals[i] = -1;
                  }
              }
          }
      }
      System.out.println("Meat: \t\t" + (System.currentTimeMillis() - startTime));
  
      if(naturals[0] == 1) {
          naturals[0] = -1;
      }
  
      /* list primes */
      List list = new ArrayList();
      for (int i = 0; i &lt; naturals.length; i++) {
          if(-1 != naturals[i])
              list.add(naturals[i]);
      }
      System.out.println("Listing: \t" + (System.currentTimeMillis() - startTime));
  
      /* create the return int array */
      int size = list.size();
      int k = 0;
  
      /* tricky tricky :) */
      if(start &lt;= 2) {
          size += 1;
          k = 1;
      }
  
      int[] primes = new int[size];
  
      if(start &lt;= 2) {
          primes[0] = 2;
      }
  
      for (Iterator iterator = list.iterator(); iterator.hasNext();) {
          primes[k++] = ((Integer) iterator.next()).intValue();
      }
  
      System.out.println("Preparing end: \t" + (System.currentTimeMillis() - startTime));
      return primes;
      }
  }
  </code></pre>