title: Which is the quickest of prime generating algorithms?
body: <p>I was working on an algorithm in Java to find all primes up to a certain number. It was supposed to be an improvement of an earlier method of doing so, which was the following:</p>
  
  <pre><code>public static int[] generatePrimesUpTo(int max)
  {
      int[] primes = new int[max];
      primes[0]=2;
      int p = 1;
      for (int i=3;i&lt;max;i+=2)
      {
          if (isPrime(i))
          {
              primes[p]=i;
              p+=1;
          }
      }
      return primes;  
  }
  
  public static boolean isPrime(int a)
  {
      for (int i=3;i&lt;((int)Math.sqrt(a)+1);i+=2)
      {
          if (a%i==0)
              return false;
      }
      return true;
  }
  </code></pre>
  
  <p>Which just checks for a number N wether or not it is divisible by a smaller number, starting at 2 and ending at sqrt(N).</p>
  
  <p>Now the new approach was to divide N only by smaller prime numbers which the algorithm had found earlier. I thought it would speed up the process quite a lot since it would have to do a lot less calculations.</p>
  
  <pre><code>public static int[] generatePrimes(int num)
  {
      int[] primes = new int[num];
      int p = 3;
      primes[0] = 2;
      primes[1] = 3;
      primes[2] = 5;
      boolean prime;
      for (int i=7;i&lt;num;i+=2)
      {
          prime = true;
          for (int j=0;primes[j+1]&lt;(Math.sqrt(i)+1);j++)
          {
              if (i%primes[j]==0)
              {
                  prime = false;
                  break;
              }
          }
          if (prime)
          {
              primes[p]=i;
              p++;
          }
      }
      return primes;
  }
  </code></pre>
  
  <p>However, there seems to be almost no difference in speed for Nmax = 10^7. 
  For Nmax = 10^8 the new one was 20% faster, but my computer was more active during the calculation of the old one and I tried 10^8 only once.</p>
  
  <p>Could anyone tell me about why this new approach isn't that much faster? Or what I could do to improve the algorithm more?</p>
  
  <p>Thanks in advance!</p>