Само по себе получение массива простых чисел — задача несложная. Но она усложняется, если есть ограничение по времени. В моем случае требуется получить массив простых чисел из диапазона от -1'000'000 до 1'000'000 (включая границы), уложившись в 1 секунду (желательно с запасом) и при использовании не более 256 Мб оперативной памяти.

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

Очевидно, что ограничение на использование не более 256 Мб оперативной памяти мне никак не помешает, так как даже если бы в указанном диапазоне был бы миллион простых чисел, то в памяти они заняли бы около 4 Мб (я работаю в программе с числами типа long int), что даже и близко не приближается к нарушению этого условия. Думаю, понятно, что это рассуждение касается настольных компьютеров.

В реализации я решил использовать не статический, а динамический массив. При этом я буду использовать шаблон класса std::vector, который в C++ используют чаще других альтернатив, если требуется работа с динамическим массивом.

Функция проверки простоты числа

Эту функцию я разбирал в предыдущем посте (она написана по алгоритму перебора делителей без каких-либо оптимизаций), вот код:

bool isPrime(long int num)
{
    if (num < 2) return false;
    
    for (long int d{ 2 }; d < num; d++)
        if (num % d == 0) return false;

    return true;
}

Замер времени работы программы

Существует множество способов замерить время работы всей программы или одной из ее частей. Сейчас для этого в C++ часто используют библиотеку chrono, которая стала частью стандартной библиотеки C++, начиная со стандарта C++11.

Использовать возможности библиотеки chrono тоже можно очень по-разному. Я для этого взял класс Timer из известного бесплатного учебника learncpp.com. Вот его код:

#include <chrono>

class Timer
{
    // псевдонимы типов, чтобы сделать использование сложных типов легче
    using Clock = std::chrono::steady_clock;
    using Second = std::chrono::duration<double, std::ratio<1>>;
    // начало отсчета времени
    std::chrono::time_point<Clock> m_beg { Clock::now() };
public:
    void reset()
    {
        m_beg = Clock::now();
    }
    double elapsed() const
    {
        return std::chrono::duration_cast<Second>(Clock::now() - m_beg).count();
    }
};

Отсчет времени начнется при создании объекта этого класса. Метод elapsed возвратит количество затраченного на момент вызова метода времени в секундах. Количество времени представляется вещественным числом типа double.

Простая реализация получения массива простых чисел

Вот код, пока без каких-либо оптимизаций и с замером времени:

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

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

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

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

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

    for (long int num{ 2 }; num <= 1'000'000; num++)
    {
        if (isPrime(num))
        {
            primes.push_back(num);
        }
    }

    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 байта

    return 0;
}

В этой программе я перебираю в цикле целые числа от 2 до 1'000'000 (включая границы) и проверяю каждое из этих чисел на простоту. Целые числа, меньшие 2, не являются простыми по определению. Простые числа помещаю в вектор (динамический массив) primes.

Всего в указанном диапазоне целых чисел содержится 78'498 простых чисел. Первое из этих простых чисел — 2, последнее — 999'983.

Результаты замера времени

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

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

88.0457
88.5963
88.1466
88.6212
88.0022

То есть описанная выше простая реализация по времени не укладывается не то что в одну секунду (что требуется по условиям задачи), но даже не укладывается в одну минуту.

Продолжение следует

Если мне удастся выкроить время, то я напишу в отдельном посте, как мы решили эту задачу с учетом ограничения по времени в одну секунду. Вместо вышеуказанного простого алгоритма мы использовали Решето Эратосфена.