title: Finding prime numbers with the Sieve of Eratosthenes (Originally: Is there a better way to prepare this array?)
body: <p><strong>Note:</strong> Version 2, below, uses the Sieve of Eratosthenes.  There are several answers that helped with what I originally asked.  I have chosen the Sieve of Eratosthenes method, implemented it, and changed the question title and tags appropriately.  Thanks to everyone who helped!</p>
  
  <h2>Introduction</h2>
  
  <p>I wrote this fancy little method that generates an array of int containing the prime numbers less than the specified upper bound.  It works very well, but I have a concern.</p>
  
  <h2>The Method</h2>
  
  <pre><code>private static int [] generatePrimes(int max) {
      int [] temp = new int [max];
      temp [0] = 2;
      int index = 1;
      int prime = 1;
      boolean isPrime = false;
      while((prime += 2) &lt;= max) {
          isPrime = true;
          for(int i = 0; i &lt; index; i++) {
              if(prime % temp [i] == 0) {
                  isPrime = false;
                  break;
              }
          }
          if(isPrime) {
              temp [index++] = prime;
          }
      }
      int [] primes = new int [index];
      while(--index &gt;= 0) {
          primes [index] = temp [index];
      }
      return primes;
  }
  </code></pre>
  
  <h2>My Concern</h2>
  
  <p>My concern is that I am creating an array that is far too large for the final number of elements the method will return.  The trouble is that I don't know of a good way to correctly guess the number of prime numbers less than a specified number.</p>
  
  <h2>Focus</h2>
  
  <p>This is how the program uses the arrays.  This is what I want to improve upon.</p>
  
  <ol>
  <li>I create a temporary array that is
  large enough to hold every number
  less than the limit.</li>
  <li>I generate the prime numbers, while
  keeping count of how many I have
  generated.</li>
  <li>I make a new array that is the right
  dimension to hold just the prime
  numbers.</li>
  <li>I copy each prime number from the
  huge array to the array of the
  correct dimension.</li>
  <li>I return the array of the correct
  dimension that holds just the prime
  numbers I generated.</li>
  </ol>
  
  <h2>Questions</h2>
  
  <ol>
  <li>Can I copy the whole chunk (at once) of
  <code>temp[]</code> that has nonzero
  elements to <code>primes[]</code>
  without having to iterate through
  both arrays and copy the elements
  one by one?</li>
  <li>Are there any data structures that
  behave like an array of primitives
  that can grow as elements are added,
  rather than requiring a dimension
  upon instantiation?  What is the
  performance penalty compared to
  using an array of primitives?</li>
  </ol>
  
  <hr>
  
  <p>Version 2 (thanks to <a href="https://stackoverflow.com/users/22656/jon-skeet">Jon Skeet</a>):</p>
  
  <pre><code>private static int [] generatePrimes(int max) {
      int [] temp = new int [max];
      temp [0] = 2;
      int index = 1;
      int prime = 1;
      boolean isPrime = false;
      while((prime += 2) &lt;= max) {
          isPrime = true;
          for(int i = 0; i &lt; index; i++) {
              if(prime % temp [i] == 0) {
                  isPrime = false;
                  break;
              }
          }
          if(isPrime) {
              temp [index++] = prime;
          }
      }
      return Arrays.copyOfRange(temp, 0, index);
  }
  </code></pre>
  
  <hr>
  
  <p>Version 3 (thanks to <a href="https://stackoverflow.com/users/3333/paul-tomblin">Paul Tomblin</a>) which uses the <a href="http://en.wikipedia.org/wiki/Sieve%5Fof%5FErastosthenes" rel="nofollow noreferrer">Sieve of Erastosthenes</a>:</p>
  
  <pre><code>private static int [] generatePrimes(int max) {
      boolean[] isComposite = new boolean[max + 1];
      for (int i = 2; i * i &lt;= max; i++) {
          if (!isComposite [i]) {
              for (int j = i; i * j &lt;= max; j++) {
                  isComposite [i*j] = true;
              }
          }
      }
      int numPrimes = 0;
      for (int i = 2; i &lt;= max; i++) {
          if (!isComposite [i]) numPrimes++;
      }
      int [] primes = new int [numPrimes];
      int index = 0;
      for (int i = 2; i &lt;= max; i++) {
          if (!isComposite [i]) primes [index++] = i;
      }
      return primes;
  }
  </code></pre>