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

• Gilbert Le Blanc: 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.

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.