Outputting prime numbers between two numbers

Question

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;
        }
}

Answer 1

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.