Решето Эратосфена — реализация, возвращающая некоторые непростые значения?

Я реализовал решето Эратосфена на Java из псевдокода:

public static void sieveofEratosthenes(int n) {
    boolean numArray[];

    numArray = new boolean[n];
    for(int i = 0; i < n; i++)
        numArray[i] = true;

    int a = 0;

    for(int i = 2; i < Math.sqrt((double)n); i++) {
        if(numArray[i])  {
            for(int j = (int)Math.pow(i, 2); j < n; a++) {
                numArray[j] = false;
                j += (a * i);
            }
        }
    }

    for(int i = 2; i < n; i++) {
        if(numArray[i])
            System.out.println(i);
    }
}

Вывод, который он дает мне, когда мне 15 лет:

2
3
5
7
8
11
12
13
14

Почему некоторые из этих значений неверны? Я считаю, что моя ошибка заключается в том, как я определяю и использую массив bool. Спасибо!


java math primes sieve
person Tetramputechture    schedule 22.08.2014    source источник
comment
Как вы думаете, что делает ваш внутренний цикл (с индексом j)?   -  person Kon    schedule 22.08.2014

Ответы (4)


arrow_upward
4
arrow_downward 

        for(int j = (int)Math.pow(i, 2); j < n; a++) {
            numArray[j] = false;
            j += (a * i);
        }

должен прочесть

        for(int j = (int)Math.pow(i, 2); j < n; j+=i) {
            numArray[j] = false;
        }
person BevynQ    schedule 22.08.2014

arrow_upward
2
arrow_downward

Принцип работы SoE заключается в том, что он берет каждое число и «удаляет» все следующие за ним числа, которые на него делятся. Таким образом, каждое число x + k*x, где k > 0. Это можно сделать, просто добавив x к начальному x^2, а затем последовательно добавляя к нему x. Здесь:

for(int j = (int)Math.pow(i, 2); j < n; a++) {
    numArray[j] = false;
    j += (a * i);
}

Вы добавляете не x, а a*x, поэтому вы пропустите некоторые числа по мере увеличения a (таким образом, вы удалите 4,6 , 10, 16 и т. д., см. шаблон? он добавляет 2, 4, 6 и т. д. к начальному значению), поэтому вы должны придерживаться:

for(int j = (int)Math.pow(i, 2); j < n; j+=i) {
    numArray[j] = false;
}
person Mateusz Dymczyk    schedule 22.08.2014

arrow_upward
0
arrow_downward

Проблема в линии

 j += (a * i);

В цикле этот оператор постепенно умножает j на a*i и добавляет его на j. Итак, замените приведенную выше строку на,

 j = (a * i);

Это сработает. И да, инициализировать

a=2

потому что мы не хотим, чтобы numarray[0] или numarray[1] инициализировались или использовались. Прокомментируйте, если есть какие-либо вопросы. Спасибо

person Raj Kantaria    schedule 22.08.2014
comment
Кроме того, a необходимо повторно инициализировать внутри цикла for (int i...). Попробуйте и посмотрите, что произойдет, если вы забудете это сделать. - person ajb; 22.08.2014
comment
да, он будет инициализирован 2 после for(int j...) и внутри цикла for(int i....). - person Raj Kantaria; 22.08.2014

arrow_upward
0
arrow_downward

Это не относится напрямую к вашему вопросу, но, поскольку на него уже был дан ответ, я не вижу смысла повторять его. Однако, глядя на ваш код, я предлагаю использовать целочисленное умножение вместо Math.pow и Math.sqrt, чтобы получить немного лучшую производительность, например:

for(int i = 2; i*i < n; i++) {
    if(numArray[i])  {
        for(int j = i*i; j < n; j += i) {
            numArray[j] = false;
        }
    }
}

Следует признать, что эти вызовы будут выполняться только один раз за итерацию внешнего цикла, поэтому улучшение может быть не очень значительным. Но вызов Math.pow и Math.sqrt, вероятно, потребует гораздо больше вычислительных ресурсов, чем одно целочисленное умножение. Кроме того, если Java выполняет достаточно сложную оптимизацию, i*i может вычисляться только один раз и использоваться в обоих местах, экономя еще больше вычислительных циклов. В этом случае также отсутствует риск переполнения целого числа, поскольку i*i ограничено сверху целым числом n.

person andand    schedule 22.08.2014