В предыдущем посте по этой теме я написал программу на C++, создающую массив простых чисел, опираясь на самые простые алгоритмы (функция проверки простоты числа с помощью перебора делителей вызывается для каждого числа из заданного диапазона). Я старался не использовать каких-либо оптимизаций.

Та программа успешно создала массив простых чисел из диапазона от -1'000'000 до 1'000'000 (включая границы) в количестве 78'498 штук. Однако, она не уложилась в 1 секунду (требуется по условиям стоящей передо мной задачи). Ее работа заняла 88 секунд с хвостиком на моем компьютере.

Для решения задачи с учетом ограничения по времени в 1 секунду (есть еще ограничение по количеству используемой оперативной памяти не более 256 Мб) я решил использовать Решето Эратосфена.

Решето Эратосфена

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

В википедии пишут, что в то время математик, следуя рассматриваемому алгоритму, выписывал все числа в диапазоне от 2 до некоторого заданного целого числа (включая границы) на дощечку, покрытую воском. Дощечку прокалывали в тех местах, где были написаны составные (не простые, по-английски «composite») числа. Простые числа оставались непроколотыми. В результате табличка становилась похожа на решето (по-английски «sieve»), что отразилось в названии алгоритма.

Идея этого алгоритма состоит в последовательном накладывании определенных фильтров на выписанные на дощечку числа. Например, сначала вычеркнем (проколем) все числа, кратные двум (четные), кроме двойки. Это первый фильтр. Затем вычеркнем все числа, кратные трем, кроме тройки. Это второй фильтр. И так далее.

Авторы многих более поздних алгоритмов, использующих фильтрацию, традиционно любят в названиях своих алгоритмов использовать слово «решето». Например, Решето Сундарама, Решето Аткина и так далее.

Для своей реализации я переформулировал алгоритм «Решето Эратосфена» следующим образом:

  1. Выпишите все целые числа от 2 до заданного максимального числа (включая границы).
  2. Возьмите первое невычеркнутое число (это будет 2) — оно является простым.
  3. Вычеркните все числа, кратные этому числу, кроме него самого.
  4. Найдите следующее невычеркнутое число и повторите шаг 3.
  5. Повторяйте этот процесс, пока очередное выбранное для фильтра число не превысит заданное максимальное число.

Я постарался реализовать простейший вариант, без каких-либо оптимизаций. Конечно, за прошедшие две тысячи лет люди придумали огромное количество разных улучшений к этому алгоритму. Но прибегать к ним я буду, если самая простая версия не уложится в 1 секунду.

Реализация на C++

Реализацию получения массива простых чисел по алгоритму «Решето Эратосфена» я решил выделить в функцию с названием getPrimes. Сначала я хотел передавать в эту функцию только заданное максимальное число maxNum и возвращать полученный массив простых чисел. Но в итоге больше всего мне понравился вариант, при котором я передаю в эту функцию (по ссылке) созданный вовне массив для простых чисел primes, а функция лишь заполняет этот массив, а не создает его сама.

Вот какой у меня получился код:

void getPrimes(std::vector<long int>& primes, long int maxNum)
{
    // создать массив (решето) типа bool и заполнить его значениями true,
    // то есть сначала все числа не вычеркнуты (считаем их пока что простыми)
    bool* sieve = new bool[maxNum + 1]; // учесть нулевой индекс
    for (long int num{}; num <= maxNum; num++)
        sieve[num] = true;

    // заполнить переданный в функцию вектор primes (простые числа),
    // для этого переберем числа от 2 до maxNum (включая границы)
    for (long int num{ 2 }; num <= maxNum; num++)
    {
        // если выбранное на очередном шаге число не вычеркнуто (простое)
        if (sieve[num])
        {
            // записать простое число num в вектор primes
            primes.push_back(num);
            // вычеркнуть числа 2num, 3num, 4num и так далее,
            // так как они являются составными (не простыми)
            for (long int comp{ num + num }; comp <= maxNum; comp += num)
                sieve[comp] = false;
        }
    }

    // само решето нам далее не понадобится, освободить память
    delete[] sieve;
}

Для реализации решета sieve я не использую std::vector, так как внутри функции размер решета будет назначен при его создании и потом меняться не будет. Поэтому, думаю, незачем для решета использовать целый объект класса std::vector; решил обойтись обычным динамическим массивом с элементами типа bool. При этом важно не забыть освободить память, когда она уже будет не нужна (у меня это сделано в конце функции).

Числа, записанные на дощечке, в моей реализации представлены индексами массива sieve. Элементы sieve[0] и sieve[1] использоваться не будут. Для хранения элемента sieve[maxNum] пришлось выделить память под maxNum + 1 элементов, так как индексы начинаются с нуля.

Невычеркнутые числа помечаются значением true, вычеркивание реализуется записью в элемент решета значения false. При создании решета все числа помечаются значением true.

После создания решета перебираем в цикле его элементы от sieve[2] до sieve[maxNum] (включая границы). Название переменной comp образовано от слова «composite» (по-русски «составной»), то есть это составные (не простые) числа. Простые числа записываем в вектор primes. Числа, кратные текущему выбранному числу num, помечаем в решете значением false (вычеркиваем).

Тот же код без комментариев:

void getPrimes(std::vector<long int>& primes, long int maxNum)
{
    bool* sieve = new bool[maxNum + 1];
    for (long int num{}; num <= maxNum; num++)
        sieve[num] = true;

    for (long int num{ 2 }; num <= maxNum; num++)
    {
        if (sieve[num])
        {
            primes.push_back(num);
            for (long int comp{ num + num }; comp <= maxNum; comp += num)
                sieve[comp] = false;
        }
    }

    delete[] sieve;
}

Тестирование и замер времени

Вот какой получился код программы в целом (копировать функцию getPrimes я не буду, просто обозначу место ее вставки):

#include <iostream>
#include <vector>
#include <chrono>

// код класса Timer
// ...

// код функции getPrimes
// ...

int main()
{
    std::vector<long int> primes;

    Timer t;                               // начало отсчета времени

    getPrimes(primes, 1'000'000);

    std::cout << t.elapsed() << '\n';      // потрачено времени в секундах
    std::cout << primes.size() << '\n';    // 78'498
    std::cout << primes.front() << '\n';   // 2
    std::cout << primes.back() << '\n';    // 999'983
    std::cout << sizeof(int) << '\n';      // 4 байта
    std::cout << sizeof(long int) << '\n'; // 4 байта
    std::cout << sizeof(bool) << '\n';     // 1 байт

    return 0;
}

Про замеры времени и класс Timer я подробно писал в предыдущем посте. Напомню, что для его работы нужна стандартная библиотека chrono.

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

0.0099187
0.0113079
0.0117145
0.0098663
0.0098984

Примем, что на моем компьютере время выполнения задачи получения массива простых чисел в диапазоне от -1'000'000 до 1'000'000 (включая границы) по алгоритму «Решето Эратосфена» составляет примерно 0,01 секунды. Это соответствует условиям задачи (уложиться в 1 секунду), причем с запасом. Кроме того, можно сделать вывод, что эта версия кода быстрее предыдущей примерно в 8800 раз (88 / 0,01).

Вот она, сила математики 💪 и знания алгоритмов.

В плане использования оперативной памяти в этой версии программы на решето уйдет примерно 1 Мб (один миллион элементов массива типа bool, каждый из которых согласно стандарта C++ занимает по 1 байту). Прибавим место под 78'498 простых чисел, каждое из которых занимает по 4 байта (всего 313’992 байта). В сумме оцениваю использование оперативной памяти этой версией программы примерно в 1,3 Мб. Это с лихвой удовлетворяет условиям задачи (не более 256 Мб).

Окончание следует

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