# 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{
String[] in = new String[t];
for(int i=0; i<t; i++){
}
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();
}
}
}

• What are the magic numbers 31622 and 31623 doing in your code?
– Mast
Jul 5, 2016 at 22:42
• I thought that the prime factor for any number n cannot exceed sqrt(n) and one billion is the maximum input so 31622. Besides inconvenience to other users who want to change constants, do magic numbers have any disadvantages w.r.t program performace?! Jul 7, 2016 at 19:11

### 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]) {

Also, rather than trial division, consider using a sieve again on the range from m to n.
• @GauravSofat Private does not improve performance as far as I know. It improves maintainability in the sense that it keeps other users from accessing data or methods in ways that were not intended. In that particular case, I was probably using it because calling generatePrimesInSegment requires that generatePrimes be called first. It's possible that the API needs work. Looking at it now, there's a couple other things that I might change. Jul 7, 2016 at 17:11