что вы делите только на простые числа.

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

Плохо то, что вы делите наall найденные простые числа, то есть все простые числа меньше, чем у кандидата. Это означает, что для наибольшего простого числа меньше одного миллиона, 999983, вы делите на 78497 простых чисел, чтобы узнать, что это число является простым числом. Это большая работа. Фактически, настолько много, что работа, потраченная на простые числа в этом алгоритме, составляет около 99,9% всей работы при переходе к миллиону, большую часть - для более высоких пределов. И этот алгоритм почти квадратичный, чтобы найти простые числаn таким образом, вы должны выполнить около

n² / (2*(log n)²)

подразделения.

Простое улучшение - остановить разделение раньше. Позволятьn составное число (то есть число, большее 1, с делителями, отличными от 1, иn), и разрешиd быть делителемn.

Сейчас,d быть делителемn Значит этоn/d является целым числом, а также делителемn: n/(n/d) = d. So we can naturally group the divisors of n на пары, каждый делительd рождает пару(d, n/d).

Для такой пары есть две возможности:

d = n/d, which means n = d², or d = √n. The two are different, then one of them is smaller than the other, say d < n/d. But that immediately translates to d² < n or d < √n.

Так или иначе, каждая пара делителей содержит (по крайней мере) один, не превышающий√nследовательно,if n is a composite number, its smallest divisor (other than 1) does not exceed √n.

Таким образом, мы можем остановить пробное разделение, когда мы достигнем√n:

private static boolean checkMod( int num) {
    for (int i : primes){
        if (i*i > n){
            // We have not found a divisor less than √n, so it's a prime
            return true;
        }
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

Примечание: это зависит от списка простых чисел, которые повторяются в порядке возрастания. Если это не гарантировано языком, вы должны использовать другой метод, итерировать по индексу черезArrayList или что-то типа того.

Остановив пробное деление в квадратном корне кандидата для наибольшего простого числа меньше одного миллиона, 999983, теперь нам нужно только разделить его на 168 простых чисел ниже 1000. Это намного меньше работы, чем ранее. Прекращение пробного деления в квадратном корне и деление только на простые числа настолько же хорошо, насколько это возможно для пробного деления, и требует

2*n^1.5 / (3*(log n)²)

подразделения, дляn = 1000000это фактор около 750, неплохо, не так ли?

Но это все еще не очень эффективный, самый эффективный способ найти все простые числа нижеn сита Простой в реализации является классическимСито Эратосфена, Это находит простые числа нижеn в операциях O (n * log log n), с некоторыми улучшениями (исключающими из рассмотрения несколько кратных простых чисел), его сложность может быть уменьшена до операций O (n). Относительно новым ситом с лучшим асимптотическим поведением являетсяСито Аткина, который находит простые числаn в операциях O (n) или с улучшением исключения кратных чисел некоторых простых чисел в операциях O (n / log log n). Сито Аткина является более сложным для реализации, поэтому вероятно, что хорошая реализация сита Эратосфена работает лучше, чем наивная реализация сита Аткина. Для реализаций одинаковых уровней оптимизации разница в производительности мала, если ограничение не становится большим (больше 1010; и весьма распространено, что на практике сито эратосфена масштабируется лучше, чем сито аткина, из-за лучших схем доступа к памяти). Поэтому я бы рекомендовал начать с сита Эратосфена и только тогда, когда его производительность не удовлетворительная, несмотря на честные усилия по оптимизации, углубиться в сито Аткина. Или, если вы не хотите реализовывать это самостоятельно, найдите хорошую реализацию, которую кто-то уже серьезно настроил.

Я углубился в подробностиответ с немного другой настройкой, где проблема заключалась в поиске n-го простого числа. Некоторые реализации более или менее эффективных методов связаны с этим ответом, в частности одна или две пригодные для использования (хотя и не очень оптимизированные) реализации Решета Эратосфена.