First n primes optimization

Question

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 >= 1) {
         System.out.print("First "+n+" prime numbers are: \n");
         System.out.println(2);
      }

      for (int i = 2; i <=n;) {
         for (int j = 2; j <= 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?

Answer 1

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.

Answer 2

Don't print extras

You have

         System.out.print(2 + ", ");

and

            System.out.print(num + ", ");

Instead try

         System.out.print(2);

and

            System.out.print(", " + num);

and at the end

        System.out.println(".");

Moving the comma before the current number works better as it is easier to treat the first result differently than the last result. Since the first result is known beforehand (2). Also, you only have to check if one result is first. You have to check all the results to see if they are last.

No even primes past 2

    List<Integer> primes = new ArrayList<>();

    if (n >= 1) {
        primes.add(2);
        System.out.print(2);

        if (n >= 2) {
            primes.add(3);
            System.out.print(", " + 3);
        }
    }

    int candidate = 1;
    int interval = 2;
    while (primes.size() < n) {
        interval = 6 - interval;
        candidate += interval;

        for (int prime : primes) {
            if (prime > candidate / prime) {
                primes.add(candidate);
                System.out.print(", " + candidate);
                break;
            }

            if (candidate % prime == 0) {
                break;
            }
        }
    }

    System.out.println(".");

This version keeps a list of what primes it has found. It initializes the list with 2 and 3 if it needs that many primes.

After that, it doesn't bother to check any even numbers and skips ever third odd number. This looks like

5, 7, 11, 13, 17, 19, 23, 25,...

Note that the odd numbers it skips (9, 15, 21, ...) are all divisible by three. It does this by alternating between adding 2 and 4 to get the next number. The increment variable tracks whether the next one should add 2 or 4. Because \$6 - 2 = 4\$ and \$6 - 4 = 2\$, it alternates between them.

The primes list keeps track of its own size, so we don't need a separate counter variable (i in your original code).

I changed the names of num and j to candidate and prime in this case. I simply find candidate to be more descriptive than num. And of course this version only checks for prime factors, so the name change from j made sense.

The prime > candidate / prime expression is checking if prime is greater than the square root of candidate. If so, we haven't found a factor smaller than or equal to the square root, so we know that candidate is prime. The reason for using that form is that many implementations calculate both candidate / prime and candidate % prime at the same time. So this minimizes extra calculations.

Separate responsibilities

I left the mixing of calculations and output. That's generally bad style. You should move this into a method and return primes. Then iterate over primes to generate the output.

    StringBuilder output = new StringBuilder();
    for (int prime : generatePrimes(n)) {
         output.append(prime);
         output.append(", ");
    }

    output.setLength(output.length() - 2);
    output.append('.');

    System.out.println(output.toString());

This version will produce the same output as the corrected version of your original.

Or just use the join version suggested by @ChatterOne.

    System.out.println(String.join(", ", generatePrimes(n)) + ".");

Shorter and easier. Not as demonstrative of the powers of a StringBuilder.

Answer 3

• First of all: I guess that int num = 3; is testing code that you forgot to remove? And Math.sqrt(num) should be Math.sqrt(i)?

• To improve efficiency: keep an array, or maybe a hashmap that has a list of non-prime numbers and in your second loop skip the check if ( num%j == 0 ) if they're in the list. If you use a hashmap it's O(1) time so I'd go for that. Also, see the sieve of Eratosthenes.

• To not print the last comma, if you don't care about not printing a number as soon as you find it, just keep an array results where you push the primes and then print them with String.join(",", results);. Alternatively, have a look at this question.