Outputting prime numbers in given ranges

Question

I coded an algorithm which shows prime numbers in the ranges provided by the user. The first line states the number of test cases. Example:

INPUT

2
1 10
1 5

OUTPUT

2
3
5
7

2
3
5

t - number of cases, n and m is the range
(t<=10)
m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space

And here is my problem, algorithm works fine, but website which test this, shows- too slow. I need less than 6s !

In my opinion, problem is in method addPrimeNumbers.

class PrimeNumbers{

    private static int m = 0;
    private static int n = 0;
    private static int t = 0;
    private static int i = 0;
    private static String beforeSeparate;
    private static Scanner sc = new Scanner(System.in);
    private static List<int[]> scope = new ArrayList<>();

    public static void main (String[] args) {
        t = Integer.valueOf(sc.nextLine());
        if (checkT(t)) {

            beforeSeparate = sc.nextLine();

            if (separate(beforeSeparate).length == 2) {
                m = separate(beforeSeparate)[0];
                n = separate(beforeSeparate)[1];
                i++;
            }
            if (checkM(m) && checkN(n) && t != 1 && n - m <= 100000) {
                int firstScope[] = {m,n};
                scope.add(firstScope);
                repeatReader();
            }
            else if (t == 1 && checkM(m) && checkN(n) && n - m <= 100000){
                int firstScope[] = {m,n};
                scope.add(firstScope);
            }
            for (int[] aScope : scope) {
                addPrimeNumbers(aScope[0], aScope[1]);
            }
        }
    }

    private static void repeatReader(){
        beforeSeparate = sc.nextLine();
        if (separate(beforeSeparate).length == 2){
            m = separate(beforeSeparate)[0];
            n = separate(beforeSeparate)[1];
            i++;
            int nextScope[] = {m,n};
            scope.add(nextScope);
            if (i < t){
                repeatReader();
            }
        }
    }

    private static void addPrimeNumbers(int i, int i1) {
        String result = "";

        for (int j = i; j <= i1 ; j++) {

            int counters = 0;
            for (int num = j; num >= i ; num--) {

                if (j % num == 0){
                    counters = counters +1;
                }
            }
            if (counters == 2){
                result = result + j + "\n";
            }
        }
        System.out.println(result);
    }

    private static boolean checkT(int i){
        return i > 0 && i <= 10;
    }

    private static boolean checkMinMax(int i) {
        return i >= 1 && i <= 1000000000;
    }

    private static boolean checkM(int i) {
        return checkMinMax(i) && n > 0 && i <= n;
    }

    private static boolean checkN(int i) {
        return checkMinMax(i) && m > 0 && i >= m;
    }

    private static int[] separate(String i){
        String twoValue[] = i.split(" ");

        m = Integer.parseInt(twoValue[0]);
        n = Integer.parseInt(twoValue[1]);
        return new int[]{Integer.parseInt(twoValue[0]), Integer.parseInt(twoValue[1])};
    }
}

Someone know, how to speed up this ?

Answer 1

Before addressing the performance problem I would like to make some general remarks:

• You validate the input values (t, m, n), but invalid numbers are simply ignored. For a programming challenge I would assume that the input values are in the specific ranges. However, if you decide to check the validity then an invalid input should produce an error message or program exception.

  Also the check is unnecessary complicated: m and n are passed to functions checkM and checkN, but those functions also refer to the class variables m and n directly. This could be simplified to

  if (1 <= m && m <= n && n <= 1000000000 && n - m <= 100000) { ... }
  

  Even better, define and use constants for those limits.

• The recursive function repeatReader is used to handle all test cases (but only if there is more than one test case). This seems unnecessary complicated to me, a simple loop would suffice.

• The logic to get two integers from the input line is duplicated in main and repeatReader.

• Several variables are declared as static class variables, but needed only locally in a function (such as m, n, beforeSeparate).

• There is no need to store all ranges in an array first, you can read each range and then produce the corresponding output.

• Scanner.nextInt() can be used to read the input into integers directly.

• In addPrimeNumbers you can print all found prime numbers directly, without concatenating them to a string first.

So the overall structure could be simplified to

import java.util.Scanner;

class PrimeNumbers {

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int numTests = sc.nextInt();
        for (int test = 1; test <= numTests; test++) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            printPrimesInRange(m, n);
            System.out.println();
        }
    }

    private static void printPrimesInRange(int low, int hi) {
        // Print prime numbers in the range low...hi
    }
}

Note that

       for (int num = j; num >= i ; num--) {

in addPrimeNumbers should be

       for (int num = j; num >= 1 ; num--) {

otherwise the result is not correct for ranges not starting at 1.

With respect to performance: Your function counts all divisors of a number, but

• one can stop the test if any non-trivial divisor has been found,
• any non-prime number \$ n \$ has a divisor which is \$ \le \sqrt n \$

Therefore this

    private static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }
        int limit = (int) Math.sqrt(n);
        for (int j = 2; j <= limit; j++) {
            if (n % j == 0) {
                return false;
            }
        }
        return true;
    }

    private static void printPrimesInRange(int low, int hi) {
        for (int n = low; n <= hi; ++n) {
            if (isPrime(n)) {
                System.out.println(n);
            }
        }
    }

would already improve the performance because the primality check for each number \$ n \$ is reduced from \$ O(n) \$ to \$ O(\sqrt n) \$.

For the range 100000 200000 this reduced the time from 43 seconds to approx 0.3 seconds on my 3.5 GHz Intel Core i5 iMac, measured with

$ time java PrimeNumbers < input > output

and for the range 999900000 1000000000 I measured 0.7 seconds.

So this might be sufficiently fast to pass the challenge. For even better performance, use sieving methods like the (segmented) sieve of Eratosthenes (see for example https://www.geeksforgeeks.org/segmented-sieve/).

Answer 2

A prime number has only two factors, 1 and itself. However, counting factors -- as you do -- is not an efficient way to detect primes. A more efficient way is to look for factors in [2, n-1]. Any factor in that range indicates a composite number with three or more factors, so the search can be stopped at that point. As @Martin R pointed out, the search only need cover [2, sqrt(n)] to find the smaller of any pair of factors. In pseudocode this looks something like:

boolean isPrime(n) {

  for i in 2 to sqrt(n) do
    if (n MOD i == 0)
      return false  // n is not prime, it has a third factor.
    endif
  endfor

  // n is prime if we get this far.
  return true

}

There is a further efficiency with even numbers. If any even number is a factor of n, then 2 is also a factor. Hence, once you have tested for 2 as a factor, you don't need to check any other even numbers as a factor. This will roughly halve the runtime.

boolean isPrime(n) {

  // Even n
  if (n MOD 2 == 0)
    return n == 2  // 2 is the only even prime number.
  endif

  // Odd n
  for i in 3 to sqrt(n) step 2 do
    if (n MOD i == 0)
      return false  // n has a third factor so it is not prime.
    endif
  endfor

  // n is an odd prime if we get this far.
  return true

}

As a minor point, if you are going to check the given input parameters, it is probably better style to use a single checkParameters() method, given that the checks are so simple.

Answer 3

In case anyone is wondering, the following does NOT work. It takes too long at roughly the point shown in the code:

public class PrimeSieve {

   public static void main( String[] args ) {
      BigInteger num = BigInteger.ZERO;
//      BigInteger end = new BigInteger( "1000000000" );
      BigInteger end = new BigInteger( "1000000" );
      while( num.compareTo( end ) < 0 ) {
         num = num.nextProbablePrime();
      }
      System.out.println( num );
   }

}

Output:

run:
1000003
BUILD SUCCESSFUL (total time: 8 seconds)