Задача программирования почти простых чисел не принята в Java

Question

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.ArrayList;



public class Main {

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String str = input.readLine();
        StringTokenizer token = new StringTokenizer(str);
        int casos = Integer.parseInt(token.nextToken());
        for (int i = 1; i <= casos; i++) {
            str = input.readLine();
            token = new StringTokenizer(str);
            long n1 = Long.parseLong(token.nextToken());
            long n2 = Long.parseLong(token.nextToken());
            int cant = (int) (n2 - n1);
            Boolean[] bool = new Boolean[1000000];
            ArrayList<Long> primos = new ArrayList<Long>();
            ArrayList<Long> casiP = new ArrayList<Long>();

            Arrays.fill(bool, Boolean.TRUE);
            for (int j = 2; j < 1000000; j += 2) {
                bool[j] = false;
            }
            primos.add(2L);

            for (int p = 3; p <= 1000; p += 2) {
                if (bool[p]) {
                    for (int j = p; j * p < 1000000; j++) {
                        bool[j * p] = false;
                    }
                    primos.add((long) p);
                }
            }
            for (int j = 1001; j <= 1000000; j += 2) {
                if (bool[j]) {
                    primos.add((long) j);
                }
            }

            for (int j = 0; j < primos.size(); j++) {
                long k = primos.get(j);
                for (long a = k * k; a < 1000000000000L; a *= k) {
                    casiP.add(a);
                }
            }

            int cont = 0;
            for (int j = 0; j < casiP.size(); j++) {
                if (casiP.get(j) >= n1 && casiP.get(j) <= n2) {
                    cont++;
                }
            }

            System.out.println(cont);
        }
    }
}

Привет, я кодировал вышеупомянутое решение для проблемы UV39 10539, используя Сито Эратосфена, как и большинство людей, однако основное отличие состоит в том, что почти все используют C++ и "читы" с такими функциями, как memset, а я даже изменил сканер Scanner с BufferedReader и даже тогда мое решение использует менее 3 секунд. Повсеместно написано, что проблемы конкурентного программирования не зависят от языка программирования, поэтому я делаю что-то не так, есть ли способ улучшить мой код или просто некоторые проблемы не могут быть приняты при использовании Java?. Я очень ценю помощь.

Answer 1

До сих пор неясно, в чем именно проблема, но ваш код расточителен, потому что он пересчитывает сита для каждой введенной пары чисел. Вам необходимо рассчитать сита только один раз, прежде чем войти в самый внешний цикл for, а затем, внутри цикла, оставить только самый последний цикл for.