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

Представьте целое число N в виде суммы минимального количества простых чисел. Слагаемые могут повторяться. Если решений несколько, выведите любое. Гарантируется, что исходное число N находится в диапазоне от 2 до 1’000’000 (включая границы). Программа должна уложиться в 1 секунду и 256 Мб памяти.

При поиске в интернете поисковые системы и нейросети часто путают эту задачу с задачей факторизации целых чисел (разложение натурального числа на произведение простых множителей). Не путайте, там — произведение и множители, здесь — сумма и слагаемые. Это разные вещи.

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

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

Я не являюсь автором использованных при решении алгоритмов, ориентировался на подсказки других людей в интернете. Программу на языке C++ писал сам.

Алгоритм решения

Алгоритм решения этой задачи в словесной форме я сформулировал так:

  1. Получить исходное целое число N. Необязательная проверка на вхождение N в заданный по условиям задачи диапазон от 2 до 1'000'000 (включая границы).

  2. Выписать в массив primes все возможные слагаемые. То есть это все простые числа в диапазоне от 2 до N (включая границы).

  3. Определить минимальное количество простых слагаемых для заданного N. Найти эти слагаемые в массиве primes и выписать их в массив addends.

  4. Отобразить содержимое массива addends в качестве решения задачи.

Для реализации массивов primes и addends я использовал шаблон std::vector. Для хранения чисел использовал тип long int.

Первый пункт алгоритма в общее время работы программы не включаю, так как получение числа N может быть реализовано получением числа от пользователя-человека. А время работы человека, очевидно, неправильно складывать со временем работы процессора компьютера. Если секунда для человека — мгновение, то для процессора секунда — вечность.

Самый затратный по времени пункт — второй. Пунктами 3 и 4 на фоне второго можно пренебречь. Реализацию второго пункта алгоритма я подробно описал в предыдущем посте. Для уменьшения затраченного времени использовал алгоритм «Решето Эратосфена». Второй пункт выделил в функцию getPrimes. В эту функцию передаю пустой массив primes и число N. Функция возвращает заполненный массив primes.

В пункте 3 алгоритма для поиска в массиве primes использую шаблон функции std::binary_search со стандартной реализацией алгоритма двоичного поиска. Это один из самых быстрых алгоритмов поиска: на каждом шаге этого алгоритма количество элементов, среди которых ведется поиск, уменьшается вдвое (поэтому алгоритм и называют «двоичным»). У этого алгоритма есть серьезное ограничение: он ведет поиск только в отсортированных данных. Однако, в нашем случае это не помеха: массив primes заполнен простыми числами по возрастанию.

Определение минимального количества простых слагаемых для заданного N опишу отдельно в подробностях далее.

Проблема Гольдбаха

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

Любопытно, что на тот момент оба этих математика давным-давно жили и работали в России, хотя родились и получили образование в Бранденбург-Пруссии и Швейцарии соответственно. То есть в то время утечка мозгов шла с Запада в Россию, а не наоборот.

Формулировка двух частей Проблемы Гольдбаха:

  1. Бинарная. Каждое четное число, большее двух, можно представить в виде суммы двух простых чисел.

  2. Тернарная. Каждое нечетное число, большее пяти, можно представить в виде суммы трех простых чисел.

Долгое время эти два предположения оставались недоказанными. Тернарная часть Проблемы Гольдбаха доказывалась разными математиками по частям и окончательно была доказана в 2013 году.

Бинарная часть Проблемы Гольдбаха до сих пор не доказана и включена в различные знаменитые списки недоказанных математических предположений. Однако, в википедии сказано, что на 2012 год правильность этого предположения была проверена для всех четных чисел, не превышающих 4×1018. То есть для диапазона чисел N от 2 до 1'000'000 (включая границы), заданного по условиям нашей задачи, считаем бинарную часть Проблемы Гольдбаха тоже доказанной.

Определение минимума простых слагаемых для N

Проблема Гольдбаха становится опорой при разложении числа N на минимум простых слагаемых, но не дает окончательного решения сразу. Например, если число можно разложить на три простых слагаемых (тернарная часть Проблемы Гольдбаха), то это не значит, что это число нельзя разложить на меньшее число слагаемых — на два или даже на одно.

Я нарисовал следующую схему для изображения окончательного алгоритма определения минимума простых слагаемых для заданного числа N. Всего в нем пять веток (соответствующие блоки обозначены розовым цветом): Схема нарисована по правилам диаграммы деятельности (activity diagram) языка UML. Для рисования схемы использован веб-сервис PlantUML. Этот веб-сервис дает возможность сохранять схему в разных форматах, я выбрал SVG (векторная графика, то есть позволяет без ущерба для качества масштабировать изображение).

Для реализации этого алгоритма я написал функцию с названием decomposeOnPrimes. Она получает заполненный массив возможных простых слагаемых primes, пустой массив addends (в него будут помещены найденные слагаемые) и число N, которое нужно разложить на простые слагаемые. Вот какой у меня получился код:

void decomposeOnPrimes(const std::vector<long int>& primes,
                       std::vector<long int>& addends, long int N)
{
    if (N % 2 == 0) // N четное?
    {
        if (N == 2) // N равно 2?
        {
            addends.push_back(2); // Одно слагаемое: 2
        }
        else                      // Два слагаемых,
        {                         // найти в primes
            for (const long int prime: primes)
            {
                if (contains(primes, N - prime))
                {
                    addends.push_back(prime);
                    addends.push_back(N - prime);
                    break;
                }
            }
        }
    }
    else            // N нечетное
    {
        if(contains(primes, N))           // N простое?
        {
            addends.push_back(N);         // Одно слагаемое: N
        }
        else if (contains(primes, N - 2))   // (N - 2) простое?
        {                                   // Два слагаемых:
            addends.push_back(2);           // 2
            addends.push_back(N - 2);       // N - 2
        }
        else                                // Три слагаемых,
        {                                   // найти в primes
            for (const long int prime: primes)
            {
                if (contains(primes, N - 3 - prime))
                {
                    addends.push_back(3);
                    addends.push_back(prime);
                    addends.push_back(N - 3 - prime);
                    break;
                }
            }
        }
    }
}

Функция contains — вспомогательная. Она очень простая, я ее написал для улучшения читаемости кода, чтобы каждый раз не писать длинный вызов стандартной функции двоичного поиска std::binary_search. Вот код функции contains:

bool contains(const std::vector<long int>& primes, long int num)
{
    return std::binary_search(primes.begin(), primes.end(), num);
}

Вышеизложенный алгоритм построен на нескольких простых рассуждениях. Если заданное число N простое, то оно и будет единственным слагаемым разложения его на простые слагаемые. Среди четных чисел простое число только одно — это число 2. Все остальные простые числа являются нечетными.

Таким образом, если заданное число N является четным, то его можно разложить либо на одно простое слагаемое (N равно 2), либо на два простых слагаемых (бинарная часть Проблемы Гольдбаха). Если заданное число N является нечетным, то его можно разложить на одно (число N простое), два или три простых слагаемых (тернарная часть Проблемы Гольдбаха).

Дополнительного обдумывания требует случай нечетного N с его разложением на два простых слагаемых. Тут нужно учесть следующее. Нечетное число можно разложить на два слагаемых только в том случае, если одно из этих слагаемых является четным, а другое — нечетным (это можно вывести из самих определений четности и нечетности). Так как оба слагаемых у нас должны быть простыми, то одним из слагаемых в рассматриваемом случае обязательно будет число 2, так как лишь это число является простым среди четных чисел. Нам остается лишь проверить на простоту число N - 2 в качестве второго слагаемого. Подробности смотрите в коде выше.

Также заставляет задуматься случай нечетного N с его разложением на три простых слагаемых. В качестве первого простого слагаемого предлагается взять число 3 (начинаем с первых простых чисел, число 2 рассмотрели в другой ветке, следующее — число 3). Число N - 3 обязательно будет четным, причина была уже упомянута выше. А четное число, как мы знаем, можно разложить на два простых слагаемых (бинарная часть Проблемы Гольдбаха). То есть задача сводится к ранее решенной.

Полный код программы и тестирование

Вот какой получился полный код программы с замером времени и тестированием:

#include <iostream>
#include <vector>
#include <algorithm> // для std::binary_search
// для замера времени работы кода
#include <chrono>
// для тестирования кода
#include <cstdlib>   // для srand, rand
#include <ctime>     // для time

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

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

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

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

int main()
{
    std::srand(std::time(nullptr));
    for (int numberOfTimes{}; numberOfTimes < 10; numberOfTimes++)
    {
        // получить от пользователя целое число N
        long int N{};
        //std::cin >> N;
        N = std::rand() % 999'999 + 2; // от 2 до 1'000'000 (включая границы)
        //std::cout << N << '\n';
        std::cout << N << " = ";

        // программа написана для чисел N, входящих в заданный диапазон
        if (N < 2 || N > 1'000'000)
        {
            std::cout << "Ошибка: " << N << " не в диапазоне [2, 1'000'000]!\n";
            return 0;
        }

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

        // получить массив простых чисел в диапазоне от 2 до N включительно
        // (простые числа, большие N, не могут быть членами разложения N)
        std::vector<long int> primes;
        getPrimes(primes, N);

        // получить разложение числа N на простые слагаемые
        std::vector<long int> addends;
        decomposeOnPrimes(primes, addends, N);

        // вывод результатов
        //std::cout << addends.size() << '\n';
        for (const long int& addend: addends)
            //std::cout << addend << ((&addend != &addends.back()) ? ' ' : '\n');
            std::cout << addend << ((&addend != &addends.back()) ? " + " : "\n");

        std::cout << t.elapsed() << '\n'; // потрачено времени в секундах
    }

    return 0;
}

Функции contains и decomposeOnPrimes подробно описаны выше в этом посте. Класс Timer описан в одном из предыдущих постов. Функция getPrimes описана в предыдущем посте.

Число N можно получить от пользователя. Но я временно, для тестирования, написал так, что при каждом запуске программы она раскладывает на простые слагаемые 10 случайных чисел из диапазона от 2 до 1'000'000 (включая границы). Для каждого разложения также замеряется время работы программы в секундах.

Результаты тестирования

Напомню, у нас на входе число из диапазона от 2 до 1'000'000 (включая границы).

Первые числа:

2 = 2
3 = 3
4 = 2 + 2
5 = 5
6 = 3 + 3
7 = 7
8 = 3 + 5
9 = 2 + 7
10 = 3 + 7
11 = 11
12 = 5 + 7
13 = 13
14 = 3 + 11
15 = 2 + 13
16 = 3 + 13
17 = 17
18 = 5 + 13
19 = 19
20 = 3 + 17

Последние числа:

999991 = 3 + 5 + 999983
999992 = 13 + 999979
999993 = 3 + 7 + 999983
999994 = 11 + 999983
999995 = 3 + 13 + 999979
999996 = 13 + 999983
999997 = 3 + 11 + 999983
999998 = 19 + 999979
999999 = 3 + 13 + 999983
1000000 = 17 + 999983

Случайные числа:

32486 = 7 + 32479
17741 = 3 + 31 + 17707
8100 = 7 + 8093
6315 = 3 + 11 + 6301
9062 = 3 + 9059
14324 = 3 + 14321
22905 = 3 + 31 + 22871
7951 = 7951
14539 = 2 + 14537
12618 = 5 + 12613

Время работы программы для любого одного числа из заданного диапазона у меня на компьютере не поднимается выше 0,02 секунды. Размер используемой памяти не поднимается выше 1,5 Мб.