TLE on SPOJ for Prime Generator (PRIME1)

The objective is to find all primes between two given numbers. It is specified that the two numbers are \$\le\$ 1 billion and the difference between the two numbers is ~100,000. We are to repeat the whole process for a \$t\$number of times, where \$t\$ is given \$\le\$ 10.

Detail of the problem: PRIME1

The following code results in Time Limit Exceeded, so please suggest optimizations.

import java.lang.*;
import java.util.*;
import java.io.*;

class PRIME1 {
    static boolean[] primesUpto(){
        boolean[] isPrime =new boolean[31623];
        for(int i=2; i<isPrime.length; i++){
            isPrime[i]=true;
        }
        for(int i=2;i<isPrime.length;i++){
            for(int j=i;j*i<isPrime.length;j++){
                isPrime[j*i]=false;
            }
        }
        return isPrime;
    }
    static boolean[] isPrime=primesUpto();
    static void listPrimes(long m, long n){
        for(long i=m; i<n+1; i++){
            for(int j=2; j<isPrime.length;j++){
                if(isPrime[j] && i%j==0) break;
                if(j==31622) System.out.println(i);
            }
        }
    }
    public static void main(String args[])throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        byte t= Byte.parseByte(br.readLine());
        String[] in = new String[t];
        for(int i=0; i<t; i++){
            in[i]=br.readLine();
        }
        for(int i=0; i<t;i++){
            StringTokenizer st = new StringTokenizer(in[i]);
            listPrimes(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()));
            System.out.println();
        }
    }
}

Avoid magic numbers

boolean[] isPrime =new boolean[31623];

This should have a constant defined. Perhaps

final long MAXIMUM_CANDIDATE = 1000000000;
    final int MAXIMUM_SMALLEST_FACTOR = (int)Math.sqrt(MAXIMUM_CANDIDATE);

I suppose that the really correct name would be MAXIMUM_SMALLEST_FACTOR_OF_ANY_NONPRIME_NUMBER_LESS_THAN_MAXIMUM_CANDIDATE, but hopefully this is clear enough.

And you may want to pass it into the method, e.g.

static boolean[] composites = primesUpto(MAXIMUM_SMALLEST_FACTOR);

and

static boolean[] primesUpto(int maximumSmallestFactor) {
        boolean[] composites = new boolean[maximumSmallestFactor + 1];

This makes the method more general.

I also changed the name from the verb isPrime to a noun name, as is consistent with object-oriented naming conventions. I also changed the direction. This allows us to eliminate the step of setting everything to true. Now the natural default of false will be correct. We only need to set the true values.

Don't do unnecessary math

for(int j=i;j*i<isPrime.length;j++){
                isPrime[j*i]=false;
            }

This does more work than is necessary. Consider

for (int j = i*i; j < composites.length; j += i) {
                composites[j] = true;
            }

This saves a multiplication every iteration (two if the compiler is dumb enough) but only replaces an increment by one with an increment by i. Two operations that will normally take the same time.

You can save even more time by adding another check.

if (!composites[i]) {
                for (int j = i*i; j < composites.length; j += i) {
                    composites[j] = true;
                }
            }

Now we only sieve out multiples of primes. So one comparison per outer loop iteration saves running the inner loop more than half the time.

for(long i=m; i<n+1; i++){

Similarly, this could be written

for (long i = m; i <= n; i++) {

Don't do in a loop what you can do outside

for(int j=2; j<isPrime.length;j++){
                if(isPrime[j] && i%j==0) break;
                if(j==31622) System.out.println(i);
            }

You check on every iteration if it is the last iteration. Consider

int j = 2;
            for (; j < composites.length; j++) {
                if (!composites[j] && i%j == 0) {
                    break;
                }
            }

            if (j == composites.length) {
                System.out.println(i);
            }

This does the same thing in effect, but it only checks once to see if the loop reached the end.

It also gets rid of the magic number.

And I added more {} and whitespace, because I find it easier to follow.

An alternative

If these changes aren't enough, you might consider changing the algorithm. You iterate over the entire array to find just the primes. Why not store just the primes in the first place? Still use the sieve to mask out the non-primes, but when you find a prime, save it.

if (!composites[i]) {
                primes.add(i);
                for (int j = i*i; j < composites.length; j += i) {
                    composites[j] = true;
                }
            }

Also, rather than trial division, consider using a sieve again on the range from m to n.

If you want to see an example of how this could work, try here. I already wrote out a solution for this. The other answer to the same question has additional explanation of the algorithm and links to a C++ solution.

StackExchange Code Review Q#133996, answer score: 4