На днях пробовал решать задачки для собеседований в некую контору. Сделал вывод, что нужно освежить в памяти некоторые базовые вещи. Одна из таких вещей — проверка числа на простоту (википедия). Программа будет на языке C++.

В интернете огромное количество источников по этой теме. Мне хотелось реализовать наиболее простой алгоритм, который будет легче запомнить. Различные оптимизации можно будет добавить позже, если будет нарушено условие по времени.

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

Есть большое количество определений простоты числа. Я сформулировал наиболее удобное для своей реализации проверки простоты числа в следующем виде.

Простое число — натуральное число, делящееся без остатка ровно на два различных натуральных делителя: на 1 и на само себя.

Натуральными называют числа, которые можно использовать для счета. То есть это целые числа. Кроме того, это только положительные числа, не отрицательные. Число 0 я буду считать натуральным числом.

Выбор типа переменной для хранения чисел

Обычно выбирают тип int. Но для моего случая это не идеальный выбор. Дело в том, что я хочу реализовать проверку простоты для чисел из диапазона от -1'000'000 до 1'000'000, включая границы. Стандарт языка C++ определяет, что под переменную типа int должно быть отведено в памяти не менее 16 битов. Большинство популярных систем по умолчанию отводит для переменных типа int в памяти 32 бита, этого мне хватит. Но если попадется редкий случай, когда система отведет под int в памяти 16 битов, то этого мне не хватит.

Напомню зависимость диапазона значений от ширины переменной для целых чисел со знаком в памяти в битах:

Биты Диапазон (включая границы)
16 -32'768 32'767
32 -2'147'483'648 2'147'483'647

Таким образом, в моем случае имеет смысл использовать либо long int (по стандарту C++ — не менее 32 битов в памяти), либо один из типов с фиксированной шириной в памяти, вроде int32_t и тому подобных. Я выбрал тип long int.

Реализация

Код функции для определения простоты заданного числа:

bool isPrime(long int num)
{
    // отрицательные числа не являются простыми, так как не натуральные
    // число 0 не простое, так как делится без остатка на любое число
    // число 1 не простое, так как имеет только один делитель — себя
    if (num < 2) return false;
    
    // проверка на простоту перебором всех делителей d
    // от 2 включительно
    // до num не включительно (на себя делится без остатка любое число)
    for (long int d{ 2 }; d < num; d++)
        // число num — не простое, так как найден третий делитель
        if (num % d == 0) return false;

    // число num — простое, так как не найден третий делитель
    return true;
}

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

Код функции для определения простоты заданного числа без комментариев:

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;
}

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

Поскольку в будущем я могу добавить в эту функцию одну или несколько оптимизаций, я подготовил для нее следующие тесты:

#include <iostream>
#include <cassert>

// определение функции isPrime
// ...

int main()
{
    // тестирование

    // отрицательные числа
    assert(isPrime(-5) == false);

    // специальные и граничные значения (числа 0, 1, 2)
    assert(isPrime(0) == false);
    assert(isPrime(1) == false);
    assert(isPrime(2) == true);

    // числа 4, 25, 1'000'000
    assert(isPrime(4) == false);
    assert(isPrime(25) == false);
    assert(isPrime(1'000'000) == false);

    // числа 3, 5, 3571, 999'983
    assert(isPrime(3) == true);
    assert(isPrime(5) == true);
    assert(isPrime(3571) == true);
    assert(isPrime(999'983) == true);

    std::cout << "Test OK\n";

    return 0;
}

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

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