4
\$\begingroup\$

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();
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ What are the magic numbers 31622 and 31623 doing in your code? \$\endgroup\$ – Mast Jul 5 '16 at 22:42
  • \$\begingroup\$ 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?! \$\endgroup\$ – Gaurav Sofat Jul 7 '16 at 19:11
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I have gone through the alternative answer and I'm in the process of writing the code again based on your mentioned suggestions... But can you brief me on why you use the modifier private so consciously, does it improve on performance in any way ?! \$\endgroup\$ – Gaurav Sofat Jul 7 '16 at 16:07
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – mdfst13 Jul 7 '16 at 17:11
  • \$\begingroup\$ I rewrote a code based on your linked solution (basically i read it and did it exactly your way ) and im still getting a TLE .The only part I modified was the way the console I/O was handled (exactly as done in my code above). \$\endgroup\$ – Gaurav Sofat Jul 7 '16 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.