4
\$\begingroup\$

What is the best practice to output a list of prime numbers between two numbers? How can I achieve a better running time? This is a solution to a SPOJ problem which is getting Time Limit Exceeded.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

class SPOJ2 {
        public static void main(String[] args) {
                try{
                        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                        int times = Integer.parseInt(reader.readLine().toString());

                        int temp=times-1;
                        String[] input_string = new String[times];
                        int[] start_number = new int[times];
                        int[] end_number = new int[times];
                        int min_start_number=0, max_end_number=0;
                        while(temp>=0){
                                input_string[temp] = reader.readLine().toString();
                                --temp;
                        }
                        temp=times-1;
                        while(temp>=0){
                                String[] array_string = input_string[temp].split("\\s");
                                start_number[temp] = Integer.parseInt(array_string[0]);
                                end_number[temp] = Integer.parseInt(array_string[1]);
                                if(min_start_number == 0 || min_start_number > start_number[temp]){
                                        min_start_number = start_number[temp];
                                }
                                if(max_end_number < end_number[temp]){
                                        max_end_number = end_number[temp];
                                }
                                if(start_number[temp] > end_number[temp]){
                                        end_number[temp] = start_number[temp]+1;
                                }
                                --temp;
                        }
                        Prime prime_object = new Prime();
                        List<Integer> output_list = prime_object.primeBetween(min_start_number, max_end_number);
                        temp = times-1;
                        while(temp>=0){
                                for(int count=0; count<output_list.size(); count++){
                                        if(output_list.get(count) >= start_number[temp] && output_list.get(count) <= end_number[temp]){
                                                System.out.println(output_list.get(count));
                                        }
                                }
                                --temp;
                                if(temp != times) System.out.println("");
                        }
                }catch(Exception e){
                        return;
                }
        }
}

class Prime {
        public List<Integer> primeBetween(int start_number, int end_number){
                int last_check_number = (int)Math.sqrt(end_number);
                int start_check_number = (int)Math.sqrt(start_number);
                List<Integer> primes_list = new ArrayList<Integer>();
                for(int count=2; count<=end_number; count++){
                        primes_list.add(count);
                }
                for(int outer_i=0; (primes_list.get(outer_i)<=start_check_number || (primes_list.get(outer_i)>start_check_number && primes_list.get(outer_i)<last_check_number)); outer_i++){
                        for(int inner_i=outer_i; primes_list.get(inner_i)<last_check_number; inner_i++){
                                int check_number = primes_list.get(inner_i);
                                for(int temp=2; (temp*check_number)<=end_number; temp++){
                                        primes_list.remove(new Integer(temp*check_number));
                                }
                        }
                }
                return primes_list;
        }
}
\$\endgroup\$
  • 3
    \$\begingroup\$ The best practice is to take your problem and break it into many tiny steps. I can't guarantee it will run faster. I can guarantee it will be easier for mere mortals to understand. \$\endgroup\$ – Gilbert Le Blanc Jun 3 '13 at 12:58
3
\$\begingroup\$

I followed my own advice, and broke the SPOJ problem into many tiny steps.

The first thing I did was create a class to hold the prime ranges that are given as input. The PrimeRange class is a basic getter/setter class for a range of numbers.

public class PrimeRange {

    private int minimum;
    private int maximum;

    public PrimeRange(int minimum, int maximum) {
        this.minimum = minimum;
        this.maximum = maximum;
    }

    public int getMinimum() {
        return minimum;
    }

    public int getMaximum() {
        return maximum;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Prime range - minimum: ");
        builder.append(getMinimum());
        builder.append(", maximum: ");
        builder.append(getMaximum());

        return builder.toString();
    }

}

Next, I created a class that would give me all of the prime numbers from a minimum value to a maximum value.

First, I calculated all of the prime numbers up to the square root of the maximum. Then, using those prime numbers, I calculated all of the prime numbers from the minimum to the maximum.

This is the fastest algorithm I can think of for calculating large prime numbers.

import java.util.ArrayList;
import java.util.List;

public class PrimeList {

    private List<Integer>   primeFactors;
    private List<Integer>   primeAnswers;

    private PrimeRange      primeRange;

    public PrimeList(PrimeRange primeRange) {
        this.primeRange = primeRange;
        this.primeFactors = new ArrayList<Integer>();
        this.primeAnswers = new ArrayList<Integer>();
        calculateDivisorPrimes();
        calculateAnswerPrimes();
    }

    private void calculateDivisorPrimes() {
        primeFactors.add(2);
        primeFactors.add(3);
        primeFactors.add(5);

        int maxValue = primeRange.getMaximum();
        int maxSqrt = (int) Math.round(Math.pow((double) maxValue, 0.5D));

        for (int test = 7; test <= maxSqrt; test += 2) {
            boolean testPassed = true;
            int sqrt = (int) Math.round(Math.pow((double) test, 0.5D));
            for (int divisor : primeFactors) {
                if (divisor > sqrt) {
                    break;
                }
                if (test % divisor == 0) {
                    testPassed = false;
                    break;
                }
            }
            if (testPassed) {
                primeFactors.add(test);
            }
        }
    }

    private void calculateAnswerPrimes() {
        int minValue = primeRange.getMinimum();
        int maxValue = primeRange.getMaximum();
        for (int test = minValue; test <= maxValue; test++) {
            boolean testPassed = true;
            int sqrt = (int) Math.round(Math.pow((double) test, 0.5D));
            for (int divisor : primeFactors) {
                if (test == 1) {
                    testPassed = false;
                    break;
                }
                if (test == divisor) {
                    break;
                }
                if (divisor > sqrt) {
                    break;
                }
                if (test % divisor == 0) {
                    testPassed = false;
                    break;
                }
            }
            if (testPassed) {
                primeAnswers.add(test);
            }
        }
    }

    public List<Integer> getPrimeAnswers() {
        return primeAnswers;
    }

}

Now that we've taken these tiny steps, we can put them together to solve the problem.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class PrimeInput implements Runnable {

    private List<PrimeRange>    primeRanges = new ArrayList<PrimeRange>();

    @Override
    public void run() {
        BufferedReader reader = new BufferedReader(new InputStreamReader(
                System.in));
        try {
            // First line contains count of subsequent lines
            String line = reader.readLine();
            int count = Integer.parseInt(line);

            // Read subsequent prime ranges
            for (int i = 0; i < count; i++) {
                line = reader.readLine();
                PrimeRange primeRange = processLine(line);
                primeRanges.add(primeRange);
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                if (reader != null) {
                    reader.close();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        for (PrimeRange primeRange : primeRanges) {
            PrimeList primeList = new PrimeList(primeRange);
            for (Integer prime : primeList.getPrimeAnswers()) {
                System.out.println(prime);
            }
            System.out.println(" ");
        }

    }

    private PrimeRange processLine(String line) {
        String[] range = line.split(" ");
        int minimum = Integer.parseInt(range[0]);
        int maximum = Integer.parseInt(range[1]);
        return new PrimeRange(minimum, maximum);
    }

    public static void main(String[] args) {
        new PrimeInput().run();
    }
}

I tested this Java application with large numbers, up to 1,000,000,000. The time was taken by the application writing numbers to System.out.

I don't know if this code is fast enough for the SPOJ.

I do know that this code is far easier to understand, because I broke the problem into tiny pieces and solved each tiny piece separately.

\$\endgroup\$

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.