First n primes optimization Pretty standard. Generates the first n primes, input via a scanner.

package main;

import java.util.Scanner;

public class Prime_Generator {
   public static void main(String args[]) {
      int n;
      int status = 1;
      int num = 3;

      Scanner scanner = new Scanner(System.in);
      System.out.print("First n primes: ");

      n = scanner.nextInt();
      if (n &gt;= 1) {
         System.out.print("First "+n+" prime numbers are: \n");
         System.out.println(2);
      }

      for (int i = 2; i &lt;=n;) {
         for (int j = 2; j &lt;= Math.sqrt(num); j++) {
            if (num%j == 0) {
               status = 0;
               break;
            }
         }
         if (status != 0) {
            System.out.println(num);
            i++;
         }
         status = 1;
         num++;
      }         
   }
}


My question:


How can I improve the efficiency of this code?
Two things:

First, you notice that if I entered "1" as an input, I will get "2," instead of "2".

Second, you check the divisibility of a number n against all numbers from 2 to sqrt(n). This is good, but you can improve it by keeping track of all prime numbers you produce. Whenever you find that p is a prime number, you add it to a list of prime numbers, call it primeList. Now whenever you want to check if n is prime, you can test n against all primes in primeList whose sqrt is less than or equal to n. This way to save on the number of primes to test.

There is a lot of advance theory on finding a prime, but for simple one this is sufficient.