Разложение числа на сумму простых чисел

@Енс · Регистрация: 16.01.2013

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

подскажите плз алгоритм)

@mutagen · 19.05.2013, 15:33

@docpas · 27.12.2016, 10:41

C++

#include<iostream> 
#include<string> 
#include<vector> 
#include<map> 
#include<iomanip> 
#include<math.h> 
#include<stdio.h> 
#include<algorithm> 
#include<cmath> 
#include<string.h> 
#include<sstream> 
#include<cstring> 
#include<fstream> 
#include<functional> 
#include<cstdio> 
#include<stack> 
#include<utility> 
#include<set> 
#include<list> 
#include<queue> 
#include<bitset>
using namespace std;
int main(){
    int num;
    cin >> num;
    cout << num/2 <<endl; //максимально возможное количество простых слагаемых.
    while(num>3){
        cout<< 2 << " ";
        num = num - 2;
    }
    cout<<num; //сами простые слагаемые
    return 0;
}

@Shamil1 · 27.12.2016, 11:23

Сообщение от Енс

подскажите плз алгоритм)

Если число нечётное, то вычитаем из него 3, делая его чётным.
Вычитаем из него все простые числа и смотрим, является ли результат простым числом.

Таким образом, мы раскладываем нечётное число на сумму трёх простых чисел, а чётное число - на сумму двух простых чисел.

echs · 29.12.2016, 17:42

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

Байт · 29.12.2016, 18:09

Не помню, то что любое четное число можно представить как сумму двух простых, это еще гипотеза, или уже доказано?

Добавлено через 2 минуты
https://ru.wikipedia.org/wiki/... 1%85%D0%B0
6 лет назад еще была проблемой...

echs · 29.12.2016, 19:14

Байт
Это еще гипотеза. Но она проверена как
минимум до 100 миллионов чисел. Моя
интуиция говорит, что она верна для любого
натурального четного числа большее 2.

Байт · 29.12.2016, 19:21

Сообщение от echs

Моя интуиция говорит, что она верна для любого натурального четного числа большее 2.

Моя тоже. Но, Увы, данная проблема не решается путем голосования.

@Shamil1 · 30.12.2016, 14:33

Сообщение от Байт

Не помню, то что любое четное число можно представить как сумму двух простых, это еще гипотеза, или уже доказано?

А зачем Вам доказательство?
Заинтересованные лица уже очень долго не могут опровергнуть эту гипотезу. Маловероятно, что Ваша программа её опровергнет.

Байт · 30.12.2016, 14:35

Сообщение от Shamil1

А зачем Вам доказательство?

Несколько странный вопрос, вы не находите?

@Shamil1 · 30.12.2016, 14:39

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

Добавлено через 2 минуты

Сообщение от Байт

Несколько странный вопрос, вы не находите?

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

Байт · 30.12.2016, 15:08

Сообщение от Shamil1

зачем Вам

Ключевое слово. Мне может многое понадобится такого, что Вам и не понять. Не вижу причин обсуждать это.
А вообще-то мне, как и всякому, кто немножко занимается математикой, просто интересно, как устроен мир. Так же, как было интересно, что доказана ВТФ (хотя я и не понимаю ее доказательства, и не собираюсь в нем разбираться, ибо жизнь коротка). Неужели Вас нисколько не тронул сам факт того, что доказательство найдено? Опять же - это лично ваше дело.
Как интересно было, что решена задача Континуума (правда, настолько странен результат ее решения, что заставляет задуматься) и многое другое.

Сообщение от Shamil1

Можете написать специальный код для случая, когда разложить на два не удалось.

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

Сообщение от Shamil1

это будет недостижимый участок кода.

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

@Shamil1 · 30.12.2016, 15:14

Сообщение от Байт

Ключевое слово. Мне может многое понадобится такого, что Вам и не понять. Не вижу причин обсуждать это.

Очевидно, имеется ввиду "в рамках данной задачи". Зачем Вам, мне, топикстартеру или ещё кому-нибудь в рамках задачи, обсуждаемой в данном топике, может понадобиться доказательство Бинарной Гипотезы Гольдбаха?

Байт · 30.12.2016, 15:36

Сообщение от Shamil1

Зачем Вам, мне, топикстартеру или ещё кому-нибудь в рамках задачи, обсуждаемой в данном топике,

А, так Вы о рамках? Ярый противник оффтопа? Тогда прошу
В защиту Оффтопа

echs · 30.12.2016, 16:26

Shamil1
Я пробовал решить эту задачу. Вот пара результатов
аналитического исследования
1. если четное число n имеет вид 2p , где p - простое число,
то n = p + p (очевидно, что можно исключить из доказательства
все эти случаи.)
2. если четное число n имеет вид 3 + p , p - простое число,
то случаи четных чисел
n + 2 = 5 + p
n + 4 = 7 + p
n + 8 = 11 + p
n + 10 = 13 + p
и так далее доказаны автоматически
3. Таким образом доказательству подлежат четные числа
вида 2ab
4. В этом случае легко наложить ограничение a < b
5. ... это исследование длинное и все не уместится
здесь, да и потребуется много времени...

Байт · 31.12.2016, 00:03

echs, Ну что вам сказать... Попытки,конечно, интересные, но они не стоят времени, потраченного на их прочтение. По этому поводу я выполняю давнишнию вашу просьбу. Хотя делаю это с большой неохотой. Пусть это будет моим новогодним подарком.

@ata · 04.01.2017, 05:39

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

Байт · 04.01.2017, 13:42

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

@ata · 04.01.2017, 18:55

Понятно, спасибо. Но мой алгоритм подходит, если ограничить глубину поиска. Да можно тупо два-три вложенных цикла написать. Ситуацию очень упростит бесконечный список простых чисел. Я такое писал на C# для какой-то задачи.

@_Ivana · 04.01.2017, 20:35

Сообщение от ata

Но мой алгоритм подходит

Да вашим волшебным алгоритмом хоть теорему Ферма, хоть все остальные теоретико-числовые гипотезы доказать можно!

Не планируете в конкуренты к Григорию Пивеню - автору НОВЫ основ математики 04.01.2017 (С)?

@Енс 0 / 0 / 0 Регистрация: 16.01.2013 Сообщений: 7
		1
	Разложение числа на сумму простых чисел 19.05.2013, 08:45. Показов 23260. Ответов 19 Метки нет (Все метки) подскажите плз алгоритм) 0

@mutagen 2586 / 2259 / 257 Регистрация: 14.09.2011 Сообщений: 5,185 Записей в блоге: 18
	19.05.2013, 15:33	2
	http://habrahabr.ru/post/122538/ 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	27.12.2016, 11:23	4
	Сообщение от Енс подскажите плз алгоритм) Если число нечётное, то вычитаем из него 3, делая его чётным. Вычитаем из него все простые числа и смотрим, является ли результат простым числом. Таким образом, мы раскладываем нечётное число на сумму трёх простых чисел, а чётное число - на сумму двух простых чисел. 1

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	29.12.2016, 17:42	5
	Shamil1 А заодно неплохо было бы сразу вычислить необходимое число простых чисел. Скорость работы программы будет много больше. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	29.12.2016, 18:09	6
	Не помню, то что любое четное число можно представить как сумму двух простых, это еще гипотеза, или уже доказано? Добавлено через 2 минуты https://ru.wikipedia.org/wiki/... 1%85%D0%B0 6 лет назад еще была проблемой... 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	29.12.2016, 19:14	7
	Байт Это еще гипотеза. Но она проверена как минимум до 100 миллионов чисел. Моя интуиция говорит, что она верна для любого натурального четного числа большее 2. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	29.12.2016, 19:21	8
	Сообщение от echs Моя интуиция говорит, что она верна для любого натурального четного числа большее 2. Моя тоже. Но, Увы, данная проблема не решается путем голосования. 1

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	30.12.2016, 14:33	9
	Сообщение от Байт Не помню, то что любое четное число можно представить как сумму двух простых, это еще гипотеза, или уже доказано? А зачем Вам доказательство? Заинтересованные лица уже очень долго не могут опровергнуть эту гипотезу. Маловероятно, что Ваша программа её опровергнет. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	30.12.2016, 14:35	10
	Сообщение от Shamil1 А зачем Вам доказательство? Несколько странный вопрос, вы не находите? 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	30.12.2016, 14:39	11
	з.ы. Можете написать специальный код для случая, когда разложить на два не удалось. На практике, это будет недостижимый участок кода. Добавлено через 2 минуты Сообщение от Байт Несколько странный вопрос, вы не находите? Нет, не нахожу. Я, действительно, не знаю, зачем Вам доказательство этой гипотезы. Просветите меня, если Вам не трудно. 0

	04.01.2017, 20:35

Опции темы

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	30.12.2016, 15:08	12
	Сообщение от Shamil1 зачем Вам Ключевое слово. Мне может многое понадобится такого, что Вам и не понять. Не вижу причин обсуждать это. А вообще-то мне, как и всякому, кто немножко занимается математикой, просто интересно, как устроен мир. Так же, как было интересно, что доказана ВТФ (хотя я и не понимаю ее доказательства, и не собираюсь в нем разбираться, ибо жизнь коротка). Неужели Вас нисколько не тронул сам факт того, что доказательство найдено? Опять же - это лично ваше дело. Как интересно было, что решена задача Континуума (правда, настолько странен результат ее решения, что заставляет задуматься) и многое другое. Сообщение от Shamil1 Можете написать специальный код для случая, когда разложить на два не удалось. Это не входит в круг моих интересов. Но в принципе попытаться было бы можно. Понятно, что это задача не совсем тривиальная. Если люди бьются над ней вот уже сотню лет. Сообщение от Shamil1 это будет недостижимый участок кода. Несколько самоуверенное утверждение. Конечно, представляя числа стандартными типами данных, задачу не решить. Как и не решить ее тупым перебором. Но, наверное, в этой области существуют тонкие утверждения, позволяющие сократить перебор в миллионы раз. Не считая того, что есть суперкомпьютеры и распределенные вычисления. Так что "рекорды" вполне возможны. Публикуются же постоянно все бОльшие и бОльшие простые числа. 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	30.12.2016, 15:14	13
	Сообщение от Байт Ключевое слово. Мне может многое понадобится такого, что Вам и не понять. Не вижу причин обсуждать это. Очевидно, имеется ввиду "в рамках данной задачи". Зачем Вам, мне, топикстартеру или ещё кому-нибудь в рамках задачи, обсуждаемой в данном топике, может понадобиться доказательство Бинарной Гипотезы Гольдбаха? 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	30.12.2016, 15:36	14
	Сообщение от Shamil1 Зачем Вам, мне, топикстартеру или ещё кому-нибудь в рамках задачи, обсуждаемой в данном топике, А, так Вы о рамках? Ярый противник оффтопа? Тогда прошу В защиту Оффтопа 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	30.12.2016, 16:26	15
	Shamil1 Я пробовал решить эту задачу. Вот пара результатов аналитического исследования 1. если четное число n имеет вид 2p , где p - простое число, то n = p + p (очевидно, что можно исключить из доказательства все эти случаи.) 2. если четное число n имеет вид 3 + p , p - простое число, то случаи четных чисел n + 2 = 5 + p n + 4 = 7 + p n + 8 = 11 + p n + 10 = 13 + p и так далее доказаны автоматически 3. Таким образом доказательству подлежат четные числа вида 2ab 4. В этом случае легко наложить ограничение a < b 5. ... это исследование длинное и все не уместится здесь, да и потребуется много времени... 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	31.12.2016, 00:03	16
	echs, Ну что вам сказать... Попытки,конечно, интересные, но они не стоят времени, потраченного на их прочтение. По этому поводу я выполняю давнишнию вашу просьбу. Хотя делаю это с большой неохотой. Пусть это будет моим новогодним подарком. 1

@ata 269 / 253 / 186 Регистрация: 28.10.2015 Сообщений: 723
	04.01.2017, 05:39	17
	Выбираем наибольшее простое число, не превышающее исходное число. Вычитаем. Рекурсивно повторяем операцию для остатка. Если простых чисел в заданном промежутке не осталось, берем меньшее простое число. Поиск в глубину. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	04.01.2017, 13:42	18
	ata, речь идет о разложение любого четного числа в сумму двух простых (бинарная гипотеза Гильберта) или разложении любого нечетного числа в сумму трех простых (тернарная гипотеза Гильберта). При этом тернарный вариант, кажется, доказан. Но из него, Увы! не следует бинарный. Вот если бы был доказан бинарный вариант, то из него тернарный следует с очевидной легкостью. 1

@ata 269 / 253 / 186 Регистрация: 28.10.2015 Сообщений: 723
	04.01.2017, 18:55	19
	Понятно, спасибо. Но мой алгоритм подходит, если ограничить глубину поиска. Да можно тупо два-три вложенных цикла написать. Ситуацию очень упростит бесконечный список простых чисел. Я такое писал на C# для какой-то задачи. 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	04.01.2017, 20:35	20
	Сообщение от ata Но мой алгоритм подходит Да вашим волшебным алгоритмом хоть теорему Ферма, хоть все остальные теоретико-числовые гипотезы доказать можно! Не планируете в конкуренты к Григорию Пивеню - автору НОВЫ основ математики 04.01.2017 (С)? 1