Программа для поиска всех простых чисел в очень большом заданном диапазоне целых чисел

Тебе дали

1 <= m <= n <= 1000000000, n-m<=100000

это очень маленькие числа. Чтобы отсеять диапазон с верхней границей n, вам нужны простые числа до √n. Здесь вы знаете n <= 10^9, так что √n < 31623, так что в худшем случае вам понадобятся простые числа до 31621. Их 3401. Вы можете сгенерировать их с помощью стандартного сита за несколько микросекунд.

Затем вы можете просто просеять небольшой диапазон от m до n, отметив кратные числам, которые вы просеивали раньше, и остановитесь, когда простое число превысит √n. Некоторого ускорения можно добиться, исключив из сита кратные числа некоторых маленьких простых чисел, но логика становится более сложной (вам нужно обрабатывать сита с маленькими m специально).

public int[] chunk(int m, int n) {
    if (n < 2) return null;
    if (m < 2) m = 2;
    if (n < m) throw new IllegalArgumentException("Borked");
    int root = (int)Math.sqrt((double)n);
    boolean[] sieve = new boolean[n-m+1];
    // primes is the global array of primes to 31621 populated earlier
    // primeCount is the number of primes stored in primes, i.e. 3401
    // We ignore even numbers, but keep them in the sieve to avoid index arithmetic.
    // It would be very simple to omit them, though.
    for(int i = 1, p = primes[1]; i < primeCount; ++i) {
        if ((p = primes[i]) > root) break;
        int mult;
        if (p*p < m) {
            mult = (m-1)/p+1;
            if (mult % 2 == 0) ++mult;
            mult = p*mult;
        } else {
            mult = p*p;
        }
        for(; mult <= n; mult += 2*p) {
            sieve[mult-m] = true;
        }
    }
    int count = m == 2 ? 1 : 0;
    for(int i = 1 - m%2; i < n-m; i += 2) {
        if (!sieve[i]) ++count;
    }
    int sievedPrimes[] = new int[count];
    int pi = 0;
    if (m == 2) {
        sievedPrimes[0] = 2;
        pi = 1;
    }
    for(int i = 1 - m%2; i < n-m; i += 2) {
        if (!sieve[i]) {
            sievedPrimes[pi++] = m+i;
        }
    }
    return sievedPrimes;
}

Использование BitSet или любого другого типа упакованного массива флагов уменьшит использование памяти и, таким образом, может дать значительное ускорение из-за лучшей локальности кеша.

Используйте BitSet вместо массива Boolean.

public static BitSet primes (final int MAX)
{
     BitSet primes = new BitSet (MAX);
     // make only odd numbers candidates...
     for (int i = 3; i < MAX; i+=2)
     {
        primes.set(i);
     }
     // ... except no. 2
     primes.set (2, true);
     for (int i = 3; i < MAX; i+=2)
     {
        /*
            If a number z is already  eliminated (like 9),
             because it is itself a multiple of a prime 
            (example: 3), then all multiples of z (9) are
            already eliminated.
        */
        if (primes.get (i))
        {
            int j = 3 * i;
            while (j < MAX)
            {
                if (primes.get (j))
                    primes.set (j, false);
                j += (2 * i);
            }
        }
    }
    return primes;
}   

Вы ДОЛЖНЫ сохранять результат в массиве? как насчет метода, который вычисляет, является ли данное целое число простым или нет, и просто вызывает его для каждого числа в {left,left+1,...,right}?

Вы всегда можете использовать смещение при доступе к массиву isNotPrime.

Учитывая m, n:

boolean[] isNotPrime = new boolean[n-m+1];

// to now if number x is primer or not
boolean xIsPrime = isNotPrime[x-m];

Здесь m - смещение.

Вы не обязаны иметь один большой массив: вы можете сохранить список найденных простых чисел и протестировать с использованием нескольких массивов, имеющих значения = array_slot + offset (уже проверенные значения). После того, как вы закончили значения от i до j, вы добавляете j-i к смещению и начинаете новый массив, начиная с J.

Вы можете удалить четные числа из своего массива, что сэкономит вам место (values ​​= array_slot * 2 - 1).

Поскольку расстояние между m и n относительно невелико, вы можете перебрать и использовать быстрый алгоритм проверки простоты для каждого числа от m до n.

Если вы разрешаете вероятностные алгоритмы, вы можете использовать тест Миллера-Рабина. Пусть M = n-m ‹= 10 ^ 5 и N = n‹ = 10 ^ 9. Сложность алгоритма грубой силы будет O (k M (log N) ^ 3), где k - константа, которая контролирует вероятностные гарантии (для практических приложений k может быть установлено равным 10).

В рамках задачи эта сложность будет около 10 ^ 9.