Outputting prime numbers in given ranges 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&lt;=10)
m and n (1 &lt;= m &lt;= n &lt;= 1000000000, n-m&lt;=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&lt;int[]&gt; scope = new ArrayList&lt;&gt;();

    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) &amp;&amp; checkN(n) &amp;&amp; t != 1 &amp;&amp; n - m &lt;= 100000) {
                int firstScope[] = {m,n};
                scope.add(firstScope);
                repeatReader();
            }
            else if (t == 1 &amp;&amp; checkM(m) &amp;&amp; checkN(n) &amp;&amp; n - m &lt;= 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 &lt; t){
                repeatReader();
            }
        }
    }

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

        for (int j = i; j &lt;= i1 ; j++) {

            int counters = 0;
            for (int num = j; num &gt;= 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 &gt; 0 &amp;&amp; i &lt;= 10;
    }

    private static boolean checkMinMax(int i) {
        return i &gt;= 1 &amp;&amp; i &lt;= 1000000000;
    }

    private static boolean checkM(int i) {
        return checkMinMax(i) &amp;&amp; n &gt; 0 &amp;&amp; i &lt;= n;
    }

    private static boolean checkN(int i) {
        return checkMinMax(i) &amp;&amp; m &gt; 0 &amp;&amp; i &gt;= 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 ?
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 &lt;= m &amp;&amp; m &lt;= n &amp;&amp; n &lt;= 1000000000 &amp;&amp; n - m &lt;= 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 &lt;= 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 &gt;= i ; num--) {


in addPrimeNumbers should be

       for (int num = j; num &gt;= 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 &lt; 2) {
            return false;
        }
        int limit = (int) Math.sqrt(n);
        for (int j = 2; j &lt;= limit; j++) {
            if (n % j == 0) {
                return false;
            }
        }
        return true;
    }

    private static void printPrimesInRange(int low, int hi) {
        for (int n = low; n &lt;= 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 &lt; 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/).