Hi, I implemented the Sieve . But it works in all case… but i get wrong answer…
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
long s = System.currentTimeMillis();
boolean[] flag = getPrimeBooleans();
// System.out.println(s - System.currentTimeMillis());
//s=System.currentTimeMillis();
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
int start = scan.nextInt();
int end = scan.nextInt();
list.add(Arrays.asList(start, end));
}
for (int i = 0; i < n; i++) {
findPrime(list.get(i).get(0), list.get(i).get(1), flag);
if (i != n - 1)
System.out.println();
}
// System.out.println(System.currentTimeMillis()-s);
}
public static void findPrime(int start, int end, boolean[] flag) {
//int c=0;
StringBuilder sb= new StringBuilder();
if (end > 100000000)
{ processMore(end, flag);}
for (int i = start; i <= end; i++) {
if (flag[i]) {
sb.append(i).append("\n");
//System.out.println(i);
//c++;
}
}
System.out.println(sb);
//System.out.println(start+" Total:"+c);
}
static void processMore(int end, boolean[] flag) {
for (int i = 100000001; i * i <= end; i = i + 2) {
if (flag[i]) {
for (int j = i * i; j <= end; j = j + i) {
// System.out.println("j:"+j);
flag[j] = false;
}
}
}
}
private static boolean[] getPrimeBooleans() {
boolean flag[] = new boolean[1000000001];
flag[2] = true;
for (int i = 3; i < flag.length; i = i + 2) {
flag[i] = true;
}
for (int i = 3; i * i <= 100000000; i = i + 2) {
if (flag[i]) {
for (int j = i * i; j <= 100000000; j = j + i) {
// System.out.println("j:"+j);
flag[j] = false;
}
}
}
return flag;
}
}