# Outputting prime numbers between two numbers

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.util.ArrayList;
import java.util.List;

class SPOJ2 {
public static void main(String[] args) {
try{

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){
--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++){
}
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;
}
}

• 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. – Gilbert Le Blanc Jun 3 '13 at 12:58

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 PrimeRange      primeRange;

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

private void calculateDivisorPrimes() {

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) {
}
}
}

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) {
}
}
}

}

}


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.util.ArrayList;
import java.util.List;

public class PrimeInput implements Runnable {

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

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

for (int i = 0; i < count; i++) {
PrimeRange primeRange = processLine(line);
}
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
}
} 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.