Решето Эратосфена для поиска простых чисел

17 июня 2022

Тэги: Collections, Java, YouTube, алгоритмы, головоломки, руководство.

Содержание

Описание алгоритма
Реализация на массиве boolean
Уменьшение количества проверок
Уменьшение объёма памяти
Финальная реализация
Выводы

Ранее я уже приводил Алгоритм поиска простых чисел методом перебора делителей. Эта реализация хороша, если вам нужно ровно N первых простых чисел. Но если вы ищете простые числа в некотором диапазоне (скажем, не превосходящие 1 000 000), то лучше воспользоваться более быстрым алгоритмом, который называется «решето Эратосфена».

Описание алгоритма

Этот алгоритм назван в честь древнегреческого учёного Эратосфена Киренского.

Алгоритм заключается в том, что изначально мы берём всё множество целых чисел в интересующем нас диапазоне, от 2 до N. Затем последовательно проходимся по этому множеству, вычёркивая каждое чётное число, т.к. оно делится на 2. После этого возвращаемся в начало и вычёркиваем все числа, делящиеся на 3, если они ещё не зачёркнуты. Затем делящиеся на следующее простое число – на 5. Затем на 7, на 11 и т. д. То есть мы «просеиваем» исходное множество целых чисел через сито. В итоге у нас останутся только простые числа.

Реализация на массиве boolean

Давайте напишем самую простую реализацию этого алгоритма. Метод getAllPrimesLessThan() на вход будет принимать размер решета sieveSize, который ограничивает сверху наш диапазон поиска. Для начала нам нужно создать массив типа boolean. Этот массив и будет нашим ситом. Если значение массива по индексу N равно true – число N простое. Если false – то нет. В начале алгоритма все элементы массива проставляем в true с помощью метода Arrays.fill(). Элементы с индексами 0 и 1 сразу ставим в false, т.к. ни 0, ни 1 не являются простыми числами.

public List<Integer> getAllPrimesLessThan(int sieveSize) {
    var sieve = new boolean[sieveSize];
    Arrays.fill(sieve, true);
    sieve[0] = false;
    sieve[1] = false;

    for (int i = 2; i < sieve.length; i++) {
        if (sieve[i]) {
            for (int j = 2; i * j < sieve.length; j++) {
                sieve[i * j] = false;
            }
        }
    }
    // ...

Затем в цикле, начиная со второго элемента, проверяем значение каждого элемента. Если элемент равен true, то запускаем вложенный цикл опять же со второго элемента до тех пор, пока произведение индексов i и j не превысит размер массива. И все элементы во вложенном цикле помечаем как false, т.е. они не являются простыми.

В конце ещё раз проходимся по «решету» и собираем простые числа в список:

    // ...
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i < sieve.length; i++) {
        if (sieve[i]) {
            primes.add(i);
        }
    }
    return primes;
}

Данный алгоритм работает раза в 3 быстрее, чем перебор делителей, о котором я писал в прошлой статье. Но его можно ещё ускорить.

Уменьшение количества проверок

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

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

Ну а вложенный цикл мы начинаем как раз с квадрата этого числа и зачёркиваем каждое число, кратное ему.

Данная оптимизация ускоряет алгоритм почти в 2 раза.

Уменьшение объёма памяти

Наиболее уязвимым местом алгоритма является тот факт, что нам нужно создавать массив под весь диапазон проверяемых чисел, тогда как в методе перебора делителей мы храним только найденные простые числа. На больших диапазонах вам может просто не хватить памяти для создания такого массива.

Но мы помним, что каждый элемент массива имеет булевый тип, т.е. может принимать только 2 значения. Для хранения такой информации достаточно всего 1 бита. То есть 1 байт памяти позволит хранить 8 элементов!

Заменим наш массив на класс BitSet, который позволяет легко оперировать отдельными битами:

Данная реализация работает ещё чуть быстрее предыдущей и почти в 2 раза быстрее изначальной.

Финальная реализация

В итоге наша реализация алгоритма поиска целых чисел с помощью «решета Эратосфена» примет следующий вид:

public List<Integer> getAllPrimesLessThan(int sieveSize) {
    var sieve = new BitSet(sieveSize);
    sieve.set(0, sieveSize - 1, true);
    sieve.set(0, false);
    sieve.set(1, false);
    for (int i = 2; i * i < sieve.length(); i++) {
        if (sieve.get(i)) {
            for (int j = i * i; j < sieve.length(); j += i) {
                sieve.set(j, false);
            }
        }
    }

    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i < sieve.length(); i++) {
        if (sieve.get(i)) {
            primes.add(i);
        }
    }
    return primes;
}

Оптимизации, которые мы применили:

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

Выводы

«Решето Эратосфена» позволяет искать простые числа в некотором диапазоне в несколько раз быстрее, чем алгоритм перебора делителей. Однако ему требуется точно знать диапазон поиска, а также нужна дополнительная память, чтобы хранить само «решето».

В случае, если диапазон поиска заранее неизвестен или у вас не хватает памяти для хранения решета и скорость поиска при этом не столь критична – используйте метод перебора делителей.

P.S. На написание статьи меня мотивировал пользователь Nik Nikita, который выступил с конструктивной критикой алгоритма перебора делителей на моём канале на YouTube.

Облако тэгов

Kotlin, Java, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.