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

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

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

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

@mutagen · 19.05.2013, 15:33

@docpas · 27.12.2016, 10:41

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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 (С)?

Новые блоги и статьи Все статьи Все блоги /
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы 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, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .

@Енс 0 / 0 / 0 Регистрация: 16.01.2013 Сообщений: 7

	Разложение числа на сумму простых чисел 19.05.2013, 08:45. Показов 26193. Ответов 19 Метки нет (Все метки) подскажите плз алгоритм) 0

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

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

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

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

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	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. ... это исследование длинное и все не уместится здесь, да и потребуется много времени... 0

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

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

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

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