Найти все разложения натурального числа на сумму простых

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

Нас интересует общее количество разложений натурального числа больше единицы на сумму простых. Сама по себе задача может быть сведена к классической проблеме о разбиении числа на слагаемые (coin change problem), решаемой рекурсивно методом динамического программирования.

Простые числа можно достаточно эффективно получить с помощью решета Эратосфена, как мы уже делали ранее.

Программа выводит найденное количество разбиений для всех чисел от 2 до введённого N и позволяет вывести все разложения для выбранного числа. Следует учесть, что уже для чисел больше 30-50 количество разложений может быть большим и вывод всех разложений чреват как замедлением, так и "падением" консоли.

Задача затрагивает целую кучку последовательностей OEIS (все они начинаются с n=0, а не с n=2, как у нас):

• A000607: основная последовательность — количество разбиений на необязательно различные простые (простые числа могут повторяться);
• A000041 - количество всех разбиений числа n;
• A000586: разбиения на различные простые (каждое простое можно использовать не более одного раза);
• A004526: максимальное количество слагаемых (просто floor(n/2), так как можно использовать только двойки) при разложении чисел;
• A051034: минимальное количество простых слагаемых, дающих в сумме n.

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

Программа выполнялась в консоли актуальной сборки Visual Studio 2019.

Это задача из списка задач на простые числа

#include <cstdlib>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <functional>

// Функция построения решета Эратосфена
std::vector<bool> sieveOfEratosthenes(int N) {
 std::vector<bool> is_prime(N + 1, true);
 if (N >= 0) is_prime[0] = false;
 if (N >= 1) is_prime[1] = false;
 for (int i = 2; i * i <= N; ++i) {
  if (is_prime[i]) {
   for (int j = i * i; j <= N; j += i) {
    is_prime[j] = false;
   }
  }
 }
 return is_prime;
}

// Получение списка всех простых чисел до N
std::vector<int> getPrimes(const std::vector<bool>& is_prime) {
 std::vector<int> primes;
 for (size_t i = 2; i < is_prime.size(); ++i) {
  if (is_prime[i]) {
   primes.push_back(static_cast<int>(i));
  }
 }
 return primes;
}

// Функция подсчёта количества разложений на сумму простых (любое количество слагаемых)
// Используем динамическое программирование (задача о разбиении на слагаемые)
std::vector<long long> countAllPrimePartitions(int N, const std::vector<int>& primes) {
 // dp[i] = количество способов разложить число i на сумму простых чисел
 std::vector<long long> dp(N + 1, 0);
 // Базовый случай: число 0 можно представить пустой суммой (1 способ)
 dp[0] = 1;
 // Классическая задача о разбиении: перебираем простые числа как "монеты"
 // Чтобы избежать повторений (разный порядок слагаемых), используем
 // внешний цикл по простым числам, внутренний - по суммам
 for (int prime : primes) {
  for (int i = prime; i <= N; ++i) {
   dp[i] += dp[i - prime];
  }
 }
 // Вычитаем пустое разложение для числа 0, но для положительных чисел
 // разложение на пустую сумму не считается
 // dp[0] оставляем как 1 для корректной работы алгоритма,
 // но при выводе для чисел > 0 это не влияет
 return dp;
}

// Функция для вывода всех разложений выбранного числа на сумму простых
void printAllPartitions(int number, const std::vector<int>& primes,
 const std::vector<long long>& count) {
 if (count[number] == 0 || number < 2) {
  std::cout << "Число " << number << " не раскладывается на сумму простых чисел\n";
  return;
 }
 std::cout << "\nВсе разложения числа " << number << " на сумму простых чисел:\n";
 std::cout << "Всего способов: " << count[number] << "\n\n";
 std::vector<int> current;
 int printed = 1;
 std::function<void(int, int)> findAllPartitions = [&](int remaining, int start_idx) {
  if (remaining == 0) { // Выводим найденное разложение
   std::cout << printed << "\t" << number << " = ";
   for (size_t i = 0; i < current.size(); ++i) {
    if (i > 0) std::cout << " + ";
    std::cout << current[i];
   }
   std::cout << std::endl;
   printed++;
   return;
  }
  for (size_t i = start_idx; i < primes.size(); ++i) {
   int prime = primes[i];
   if (prime > remaining) break;
   current.push_back(prime);
   findAllPartitions(remaining - prime, i); // i - можно использовать повторно
   current.pop_back();
  }
 };
 findAllPartitions(number, 0);
 if (--printed != count[number]) {
  std::cout << "\nПредупреждение: выведено " << printed
   << " из " << count[number] << " разложений\n";
 }
}

int main() {
 system("chcp 1251 > nul");
 int N;
 std::cout << "Введите N (рекомендуется N <= 200 для разумного времени работы): ";
 std::cin >> N;
 if (N < 2) {
  std::cout << "Ошибка: N должно быть >= 2" << std::endl;
  return 1;
 }
 // 1. Строим решето Эратосфена
 std::cout << "\nПостроение решета Эратосфена до " << N << "..." << std::endl;
 std::vector<bool> is_prime = sieveOfEratosthenes(N);
 // 2. Получаем список простых чисел
 std::vector<int> primes = getPrimes(is_prime);
 std::cout << "Найдено простых чисел: " << primes.size() << std::endl;
 // Выводим простые числа
 std::cout << "Простые числа: ";
 for (size_t i = 0; i < primes.size(); ++i) {
  std::cout << primes[i];
  if (i < primes.size() - 1) std::cout << ", ";
 }
 std::cout << "\n" << std::endl;
 // 3. Подсчитываем все разложения на сумму простых
 std::cout << "Подсчёт всех возможных разложений на сумму простых чисел..." << std::endl;
 std::vector<long long> all_ways = countAllPrimePartitions(N, primes);
 // 4. Вывод результатов
 std::cout << "Число;Количество разложений на сумму простых\n";
 for (int num = 2; num <= N; ++num) {
  std::cout << num << ";" << all_ways[num] << "\n";
 }
 //5. Все разложения для выбранного числа
 int choice;
 std::cout << "\nВведите число для вывода его разложений (0 - пропустить;\n" 
  << "учтите, что количество разложений растёт быстро): ";
 std::cin >> choice;
 if (choice >= 2 && choice <= N) {
  printAllPartitions(choice, primes, all_ways);
 }
 else if (choice != 0) {
  std::cout << "Число должно быть от 2 до " << N << std::endl;
 }
 return 0;
}

 JS-калькулятор разложения по Гольдбаху произвольного натурального числа, открыть в текущем окне/вкладке (9 Кб)

17.05.2026, 17:20 [174 просмотра]