Представить натуральное число в виде суммы простых натуральных чисел

@пунька · Регистрация: 21.09.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте.

Прошу помощи в написании алгоритма для элементарной задачи.. Заранее спасибо.

Дано натуральное число N. Представить его в виде суммы простых натуральных чисел так, чтобы произведение этих слагаемых было максимально.
Входные данные:
В единственной строке входного файла input.txt записано одно натуральное число N.
Выходные данные:
В единственную строку выходного файла output.txt нужно вывести простые числа по возрастанию с указанием их количества при разложении, т.е. <число> <колво>.
Пример:
input.txt | output.txt
5 | 2 1 3 1
30 | 3 10

@Joy · 22.09.2015, 11:06

Не по теме:

Сообщение от пунька

Прошу помощи в написании алгоритма для элементарной задачи..

забыл только упомянуть, что сложностью 40% на олимпиадном сайте...

Добавлено через 30 минут
для сайта на fpc 2.6.4

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var
  n:int64;
  a2,a3:int64;
begin
  readln(n);
  a3:=n div 3;
  n:=n mod 3;
  if n=1 then begin
    a3:=a3-1;
    n:=n+3;
  end;
  a2:=n div 2;
  if a2>0 then write('2 ',a2,' ');
  if a3>0 then write('3 ',a3);
end.

ФедосеевПавел · 22.09.2015, 11:13

наверное, здесь из двух шагов
1. Получение списка простых чисел, не превосходящих n.
2. Перебор вариантов с разложением n на слагаемые из списка и одновременной проверкой критерия максимальности произведения слагаемых.
Сейчас лень искать, но разложение на слагаемые можно найти и модифицировать под данную задачу.

@Joy · 22.09.2015, 11:27

Сообщение от ФедосеевПавел

1. Получение списка простых чисел, не превосходящих n.

если n=2 000 000 000 сколько времени список простых чисел будешь искать?

ФедосеевПавел · 22.09.2015, 11:41

Думаю, что не долго.
1. Сократить объём тестируемых чисел видом 6i-1, 6i+1 (не вижу символ "+-").
2. Проверять k на делимость из уже заполненного списка, а не от 2 до sqrt(k). А в списке уже можно ограничить рассмотрение величиной sqrt(k).

Может быть вечером попробую проверить.

Но по решению задачи мне не приходят в голову мысли, кроме как о полном переборе среди слагаемых из формируемого на 1-м шаге списка.

@Joy · 22.09.2015, 11:45

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

Добавлено через 1 минуту
ФедосеевПавел, приведено во 2 посте решение, скорость расчета 0.118с

ФедосеевПавел · 22.09.2015, 22:29

Увы, у меня не теоретическая специальность. И теорию чисел мы даже не изучали...
Если задача подразумевает использование именно этого свойства, то из-за невежества отхожу в сторону.

Добавлено через 10 часов 26 минут
----------------------------------------------------------------------------
Сразу отмечу, зная результат (свойство и алгоритм), просто направлялся по проторенному пути...
----------------------------------------------------------------------------
Да, можно доказать следующее.
Пусть дано число N, которое раскладывается на k слагаемых равных x. При этом, произведение слагаемых максимально. Не знаю, как доказать, что оптимум будет, если все слагаемые равны одному значению. Но положим, что это доказано. Тогда
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ N=k*x\\\prod x \rightarrow max\end{matrix}\right.$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ N=k*x\\x^k\rightarrow max\end{matrix}\right.$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ N=k*x\\ln(x^k)\rightarrow max\end{matrix}\right.$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ N=k*x\\k*ln(x)\rightarrow max\end{matrix}\right.$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ k=\frac{N}{x}\\k*ln(x)\rightarrow max\end{matrix}\right.$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ k=\frac{N}{x}\\\frac{N}{x}*ln(x)\rightarrow max\end{matrix}\right.$
Дифференцируем нижнее уравнение и находим его ноль
$https://www.cyberforum.ru/cgi-bin/latex.cgi?(\frac{N}{x}*ln(x))'=0$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?-\frac{N}{x^2}*ln{x}+\frac{N}{x}*\frac{1}{x}=0$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?ln{x}=1$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?x=e$

Итак, если раскладывать число N на некоторое количество одинаковых слагаемых, то максимальное произведение будет в том случае, когда слагаемые стремятся к e=2.7... Возможно, что доказательство о равенстве слагаемых для достижения оптимума должно проводится здесь, после первых результатов. Путём рассмотрения одной пары слагаемых x+d и x-d.

Выходит, что нужно искать ответ в переборе суммы из чисел 2 и 3.
Но e значительно ближе к 3, чем 2. Поэтому для решения возьмём максимальное количество 3, а остаток заполним 2.
----------------------------------------------------------
Спасибо, Joy

----------------------------------------------------------
Я попробовал свой вариант, но на числах, близких к 10^8 он притормаживал, на 10^9 уже основательно.
Тогда я решил искать простые числа через булевское "решето Эратосфена", но поленился, хотя выигрыш по сравнению с начальным моим вариантом бы был. Но дальше бы всё равно на повестку встал перебор N/2 чисел.
Так что, спасибо за подсказку.

Добавлено через 10 минут
-----------------------------------------------------------------
Нашёл это задание на олимпийском сайте среди заданий для 10 класса... Если они это действительно массово самостоятельно решают (с математическими выкладками) за короткое конкурсное время, то я восхищён. И даже завидую...

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@пунька 0 / 0 / 0 Регистрация: 21.09.2015 Сообщений: 1

	Представить натуральное число в виде суммы простых натуральных чисел 21.09.2015, 17:05. Показов 12245. Ответов 6 Метки нет (Все метки) Здравствуйте. Прошу помощи в написании алгоритма для элементарной задачи.. Заранее спасибо. Дано натуральное число N. Представить его в виде суммы простых натуральных чисел так, чтобы произведение этих слагаемых было максимально. Входные данные: В единственной строке входного файла input.txt записано одно натуральное число N. Выходные данные: В единственную строку выходного файла output.txt нужно вывести простые числа по возрастанию с указанием их количества при разложении, т.е. <число> <колво>. Пример: input.txt \| output.txt 5 \| 2 1 3 1 30 \| 3 10 0

ФедосеевПавел Модератор 8665 / 4502 / 1670 Регистрация: 01.02.2015 Сообщений: 13,931 Записей в блоге: 13
	22.09.2015, 11:13
	наверное, здесь из двух шагов 1. Получение списка простых чисел, не превосходящих n. 2. Перебор вариантов с разложением n на слагаемые из списка и одновременной проверкой критерия максимальности произведения слагаемых. Сейчас лень искать, но разложение на слагаемые можно найти и модифицировать под данную задачу. 0

ФедосеевПавел Модератор 8665 / 4502 / 1670 Регистрация: 01.02.2015 Сообщений: 13,931 Записей в блоге: 13
	22.09.2015, 11:41
	Думаю, что не долго. 1. Сократить объём тестируемых чисел видом 6i-1, 6i+1 (не вижу символ "+-"). 2. Проверять k на делимость из уже заполненного списка, а не от 2 до sqrt(k). А в списке уже можно ограничить рассмотрение величиной sqrt(k). Может быть вечером попробую проверить. Но по решению задачи мне не приходят в голову мысли, кроме как о полном переборе среди слагаемых из формируемого на 1-м шаге списка. 0

@Joy 2388 / 1300 / 1492 Регистрация: 29.08.2014 Сообщений: 4,665
	22.09.2015, 11:45
	есть доказанное свойство, что если число разбить на фиксированную группу чисел, то произведение этих чисел будет максимальным, если каждое из чисел стремится к e. Т.е. бьем на максимальное число троек и несколько двоек. Добавлено через 1 минуту ФедосеевПавел, приведено во 2 посте решение, скорость расчета 0.118с 1

ФедосеевПавел Модератор 8665 / 4502 / 1670 Регистрация: 01.02.2015 Сообщений: 13,931 Записей в блоге: 13
	22.09.2015, 22:29
	Сообщение было отмечено Памирыч как решение Решение Увы, у меня не теоретическая специальность. И теорию чисел мы даже не изучали... Если задача подразумевает использование именно этого свойства, то из-за невежества отхожу в сторону. Добавлено через 10 часов 26 минут ---------------------------------------------------------------------------- Сразу отмечу, зная результат (свойство и алгоритм), просто направлялся по проторенному пути... ---------------------------------------------------------------------------- Да, можно доказать следующее. Пусть дано число N, которое раскладывается на k слагаемых равных x. При этом, произведение слагаемых максимально. Не знаю, как доказать, что оптимум будет, если все слагаемые равны одному значению. Но положим, что это доказано. Тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ N=kx\\\prod x \rightarrow max\end{matrix}\right.$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ N=kx\\x^k\rightarrow max\end{matrix}\right.$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ N=kx\\ln(x^k)\rightarrow max\end{matrix}\right.$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ N=kx\\kln(x)\rightarrow max\end{matrix}\right.$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ k=\frac{N}{x}\\kln(x)\rightarrow max\end{matrix}\right.$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}\\ k=\frac{N}{x}\\\frac{N}{x}ln(x)\rightarrow max\end{matrix}\right.$ Дифференцируем нижнее уравнение и находим его ноль $https://www.cyberforum.ru/cgi-bin/latex.cgi?(\frac{N}{x}ln(x))'=0$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?-\frac{N}{x^2}ln{x}+\frac{N}{x}\frac{1}{x}=0$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?ln{x}=1$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?x=e$ Итак, если раскладывать число N на некоторое количество одинаковых слагаемых, то максимальное произведение будет в том случае, когда слагаемые стремятся к e=2.7... Возможно, что доказательство о равенстве слагаемых для достижения оптимума должно проводится здесь, после первых результатов. Путём рассмотрения одной пары слагаемых x+d и x-d. Выходит, что нужно искать ответ в переборе суммы из чисел 2 и 3. Но e значительно ближе к 3, чем 2. Поэтому для решения возьмём максимальное количество 3, а остаток заполним 2. ---------------------------------------------------------- Спасибо, Joy ---------------------------------------------------------- Я попробовал свой вариант, но на числах, близких к 10^8 он притормаживал, на 10^9 уже основательно. Тогда я решил искать простые числа через булевское "решето Эратосфена", но поленился, хотя выигрыш по сравнению с начальным моим вариантом бы был. Но дальше бы всё равно на повестку встал перебор N/2 чисел. Так что, спасибо за подсказку. Добавлено через 10 минут ----------------------------------------------------------------- Нашёл это задание на олимпийском сайте среди заданий для 10 класса... Если они это действительно массово самостоятельно решают (с математическими выкладками) за короткое конкурсное время, то я восхищён. И даже завидую... 0

Представить натуральное число в виде суммы простых натуральных чисел

Решение