I coded an algorithm which shows prime numbers in the ranges provided by the user. The first line states the number of test cases. Example:
INPUT
2
1 10
1 5
OUTPUT
2
3
5
7
2
3
5
t - number of cases, n and m is the range
(t<=10)
m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space
And here is my problem, algorithm works fine, but website which test this, shows- too slow. I need less than 6s !
In my opinion, problem is in method addPrimeNumbers.
class PrimeNumbers{
private static int m = 0;
private static int n = 0;
private static int t = 0;
private static int i = 0;
private static String beforeSeparate;
private static Scanner sc = new Scanner(System.in);
private static List<int[]> scope = new ArrayList<>();
public static void main (String[] args) {
t = Integer.valueOf(sc.nextLine());
if (checkT(t)) {
beforeSeparate = sc.nextLine();
if (separate(beforeSeparate).length == 2) {
m = separate(beforeSeparate)[0];
n = separate(beforeSeparate)[1];
i++;
}
if (checkM(m) && checkN(n) && t != 1 && n - m <= 100000) {
int firstScope[] = {m,n};
scope.add(firstScope);
repeatReader();
}
else if (t == 1 && checkM(m) && checkN(n) && n - m <= 100000){
int firstScope[] = {m,n};
scope.add(firstScope);
}
for (int[] aScope : scope) {
addPrimeNumbers(aScope[0], aScope[1]);
}
}
}
private static void repeatReader(){
beforeSeparate = sc.nextLine();
if (separate(beforeSeparate).length == 2){
m = separate(beforeSeparate)[0];
n = separate(beforeSeparate)[1];
i++;
int nextScope[] = {m,n};
scope.add(nextScope);
if (i < t){
repeatReader();
}
}
}
private static void addPrimeNumbers(int i, int i1) {
String result = "";
for (int j = i; j <= i1 ; j++) {
int counters = 0;
for (int num = j; num >= i ; num--) {
if (j % num == 0){
counters = counters +1;
}
}
if (counters == 2){
result = result + j + "\n";
}
}
System.out.println(result);
}
private static boolean checkT(int i){
return i > 0 && i <= 10;
}
private static boolean checkMinMax(int i) {
return i >= 1 && i <= 1000000000;
}
private static boolean checkM(int i) {
return checkMinMax(i) && n > 0 && i <= n;
}
private static boolean checkN(int i) {
return checkMinMax(i) && m > 0 && i >= m;
}
private static int[] separate(String i){
String twoValue[] = i.split(" ");
m = Integer.parseInt(twoValue[0]);
n = Integer.parseInt(twoValue[1]);
return new int[]{Integer.parseInt(twoValue[0]), Integer.parseInt(twoValue[1])};
}
}
Someone know, how to speed up this ?