How to generate huge amount of prime numbers in java?
<p>In order to solve a question I have to generate a list of prime numbers from 1 to 3000000, so I tried several ways to do this and unfortunately all failed...</p>

<p>First try: because all prime numbers bigger than 2 are odd numbers, so I first generate a list of odd numbers started with 3 called <code>allOddNums</code>. And then I generate a list of all composite numbers called <code>allComposite</code>. Then I remove all the number in <code>allComposite</code> from <code>allOddNums</code> to obtain prime numbers. Here is my code:</p>

<pre><code>/** Prime Numbers Generation
  * Tony
  */
import java.util.*;

public class PrimeNumG {
  public static void main(String[] args) {

    List &lt;Long&gt; allOddNums = new ArrayList&lt;Long&gt;();
    for (long i = 3; i &lt; 200; i += 2) {
      allOddNums.add(i);
    }

    // composite number generator:
    List &lt;Long&gt; allComposite = new ArrayList&lt;Long&gt;();
    for (long a = 2; a &lt; Math.round(Math.sqrt(3000000)); a += 2) {
      for (long b = 2; b &lt; Math.round(Math.sqrt(3000000)); b += 2) {
        allComposite.add(a*b);
      }
    }

    // remove duplicated:
    Set &lt;Long&gt; hs = new HashSet&lt;Long&gt;();
    hs.addAll(allComposite);
    allComposite.clear();
    allComposite.addAll(hs);

    // remove all composite from allRealNums = allPrime
    allOddNums.removeAll(allComposite);
    allOddNums.add(0, (long)2);

    System.out.printf("%s ", allOddNums);
    Scanner sc = new Scanner(System.in);
    int times = sc.nextInt();

    for (int i = 0; i &lt; times; i++) {
      int index = sc.nextInt();
      System.out.print(allOddNums.get(index) + " ");

    }
  }
}
</code></pre>

<p>In this case, when I need to generate a few prime numbers it works fine. However, if I want to generate until 3000000 it fails me(used up memory).</p>

<p>Second try: I searched online and find an algorithm called <code>sieve of Eratosthenes</code>. then I first generate 2, 3, 5, 7, 9...(all odd numbers + 2), then I remove every 3rd number after 3 and every 5th number after 5. The code is as below:</p>

<pre><code>/** Prime Number Generator
  * Tony
  */   
import java.util.*;

public class Solution61 {
  public static void main(String[] args) {
    List&lt;Long&gt; l1 = new ArrayList&lt;Long&gt; ();

    // l1 generator:   3 5 7 9 11 ... 
    for (long d = 3; d &lt; 100; d += 2) {
      l1.add(d);
    }

    l1.add(1, (long)2); // 2 3 5 ...

    removeThird(l1); // rm 3rd after 3

    removeFifth(l1); // rm 5th after 5, now the l1 will be prime number

    Scanner sc = new Scanner(System.in);
    int times = sc.nextInt();
    for (int i = 0; i &lt; times; i++) {
      int index = sc.nextInt();
      System.out.print(l1.get(index) + " ");


    }
  }


  /** removeThird : remove every 3rd number after 3
    * param List | return void
    */
  private static void removeThird(List&lt;Long&gt; l) {

    int i = 1;
    int count = 0;
    while (true) {


      if (count == 3) {
        l.remove(i);
        count = 1;

      }
      i ++;
      count ++;
      if (i &gt; l.size()) {
        break;
      }
    }
  }

  /** removeThird : remove every 5th number after 5
    * param List | return void
    */
  private static void removeFifth(List&lt;Long&gt; l) {

    int i = 2;
    int count = 0;
    while (true) {


      if (count == 5) {
        l.remove(i);
        count = 1;
      }
      i ++;
      count ++;
      if (i &gt; l.size()) {
        break;
      }
    }
  }

}
</code></pre>

<p>This is still not up to the task because it also runs out of memory.</p>

<p>3rd try:
I tried to generate from 1 to the 3000000, and then remove every number is the product of prime number and another number. The code is as below:</p>

<pre><code>/** print all the prime numbers less than N
  * Tony
  */

public class primeGenerator {
  public static void main(String[] args) {
    int n = 3000000;
    boolean[] isPrime = new boolean[n];
    isPrime[0] = false; // because 1 is not a prime number

    for (int i = 1; i &lt; n; i++) {
      isPrime[i] = true;
    } // we set 2,3,4,5,6...to true

    // the real number is always (the index of boolean + 1)

    for (int i = 2; i &lt;= n; i++) {
      if (isPrime[i-1]) {
        System.out.println(i);
        for (int j = i * i; j &lt; n; j += i /* because j is determined by i, so the third parameter doesn't mater*/) {
          isPrime[j-1] = false;
        }
      }
    }
  }
}
</code></pre>

<p>it still fails me, well guess 3000000 is really a big number huh? Is there any simple and brilliant rookie-friendly way to generate prime numbers below 3000000? Thx!</p>

<p>fourth try:
@jsheeran Is this code below what your answer means? when I hit 1093 it gets slower and slower and my IDE still crashed. Plz tell me if I misinterprete your approach, thx!</p>

<pre><code>/** new approach to find prime numbers
  * Tony
  */
import java.util.*;

public class PrimeG {

  /** isPrime
    * To determine whether a number is prime by dividing the candidate number by each prime in that list
    */
  static List&lt;Long&gt; primes = new ArrayList&lt;Long&gt; ();

  private static void isPrime(long n) {
    boolean condition = true;
    for (int i = 0; i &lt; primes.size(); i++) {
      if (n % primes.get(i) == 0) {
        condition = condition &amp;&amp; false;
      }
    }
    if (condition) {
      findNextPrime(n);
    }
  }

  /** findNextPrime
    * expand the list of prime numbers 
    */
  private static void findNextPrime(long n) {
    primes.add(n);
  }





  public static void main(String[] args) {
    primes.add((long)2);
    primes.add((long)3);
    primes.add((long)5);
    primes.add((long)7);

    for (int i = 8; i &lt; 3000000; i++) {
      isPrime(i);
      System.out.printf("%s", primes);
    }


  }
}
</code></pre>