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

@Енс · Регистрация: 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 (С)?

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

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

	Разложение числа на сумму простых чисел 19.05.2013, 08:45. Показов 25704. Ответов 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