Странная ошибка при использовании алгоритма Java Sieve of Eratosthenes с большими числами?

Question

Я испытываю странную проблему и ужасно отлаживаю ее.Я думал, что опубликую это здесь, чтобы получить какие-либо мнения.

public static void sieve(int limit) {

    for (int i = 2; i < limit; i ++) {

        if (mPrimes[i] == true) {

            for (int j = i*i; ((j < limit) && (j > 0)); j += i) {
                mPrimes[j] = false;
            }

        }

    }

}

(предположим, что изначально все mPrimes верны)

Вот подвох:

Когда я запускаю этоПрограмма с ограничениями 10, 100, 1000, 10000 и даже 100000, сообщает о подсчете правильного числа простых чисел ниже заданного числа, как перекрестно ссылается эта страница: http://primes.utm.edu/howmany.shtml

Однако, когда язапустить с аргументом 1000000 (один миллион), я получаю результат, который ровно на 7 от правильного значения (он сообщает 78491 вместо 78498).

Более того, все другие методы подсчета простых чисел, которые я реализовал в этой программе, сообщают правильное значение.

И вот реальная выгода: если я заменим

i*i

с

i+i

Что касается «вычеркивания» непосредственно из начального значения, вместо того, чтобы начинать с квадрата (что и сделал мой профессор в своем примере кода), это работает.

Мне остается только предположить, что с квадратом происходит что-то странное, когда я очень большой.

Есть предложения?

Answer 1

Это ошибка переполнения.1,000,000 * 1,000,000 требует больше битов, чем может вместить int (2 * 32 - 1).Вам нужно использовать длинную (2 * 64 -1).

Answer 2

Нет смысла пересекать любые числа, если i*i превышает ограничение.Таким образом, вместо длинных целых чисел, просто инициализируйте переменную strike_limit для потолка sqrt(i) и даже не пытайтесь войти в зачеркнутый цикл, если i превышает этот предел.Извините, я не знаю Java достаточно хорошо, чтобы писать код в нем, но это должно быть что-то вроде

int strike_limit = (int) (sqrt ((double) limit) + 0.5);

    if (mPrimes[i] && i < strike_limit) {
        for (int j = i*i; j < limit; j += i) {
            mPrimes[j] = false;
        }
    }

Это гарантирует вам переполнение при расчете i².Будьте внимательны при анализе угловых случаев.

Answer 3

Переменная i изначально равна 2 и увеличивается на каждом шаге, поэтому она всегда положительна.Переменная j изначально равна i × i , что положительно и увеличивается на положительное число i на каждом шаге, поэтому j всегда положительно.Почему вы проверяете j > 0 во внутреннем цикле?

Answer 4

Кроме того, чтобы избежать переполнения, внешний цикл может быть таким: for (int i = 2; i*i < limit; i++), и он будет еще быстрее (потому что любое не простое число в limit должно иметь хотя бы один простой делитель в sqrt(limit))