patternjavaMinor
Outputting prime numbers between two numbers
Viewed 0 times
outputtingnumberstwobetweenprime
Problem
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]){
end_number[temp] = start_number[temp]+1;
}
--temp;
}
Prime prime_object = new Prime();
List output_list = prime_object.primeBe
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]){
end_number[temp] = start_number[temp]+1;
}
--temp;
}
Prime prime_object = new Prime();
List output_list = prime_object.primeBe
Solution
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
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.
Now that we've taken these tiny steps, we can put them together to solve the problem.
I tested this Java application with large numbers, up to 1,000,000,000. The time was taken by the application writing numbers to
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 separatel
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 primeFactors;
private List primeAnswers;
private PrimeRange primeRange;
public PrimeList(PrimeRange primeRange) {
this.primeRange = primeRange;
this.primeFactors = new ArrayList();
this.primeAnswers = new ArrayList();
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 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 sqrt) {
break;
}
if (test % divisor == 0) {
testPassed = false;
break;
}
}
if (testPassed) {
primeAnswers.add(test);
}
}
}
public List 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 primeRanges = new ArrayList();
@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 separatel
Code Snippets
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();
}
}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;
}
}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();
}
}Context
StackExchange Code Review Q#26916, answer score: 3
Revisions (0)
No revisions yet.