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

@vlados124 · Входные данные Выходные данные

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

Ваша задача - определить, можно ли представить данное число N в виде суммы двух простых чисел.
Входные данные
В единственной строке записано единственное число N.
Выходные данные
Сумма двух простых чисел, равная N, или -1, если таковой не существует. В сумме первое число не более второго и если существует несколько таких возможных сумм - вывести ту, в которой первое слагаемое наименьшее.
Ограничения
1≤N≤1000000
Примеры

Входные данные	Выходные данные
9	2 + 7
10	3 + 7
11	-1

@bormant · 15.11.2018, 13:00

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var n, i, t: Longint;
begin
  Read(n);
  if Odd(n) then
    if IsPrime(n-2)
    then WriteLn('2 + ',n-2)
    else WriteLn(-1)
  else if n=4 then WriteLn('2 + 2')
  else begin
    i:=3; t:=n div 2;
    while (i<=t) and not (IsPrime(i) and IsPrime(n-i)) do Inc(i,2);
    if i<=t
    then WriteLn(i,' + ',n-i)
    else WriteLn(-1);
  end;
end.

IsPrime -- проверка на простоту, написать самому или взять готовую на форуме.

Добавлено через 5 минут
Если реализация IsPrime кэширует ранее вычисленные значения или основана на предварительном построении решета Эратосфена до n-2 -- будет хорошая прибавка к скорости.

Добавлено через 4 минуты
Вместо вызовов IsPrime можно сразу построить решето Эратосфена до n-2 и дальше пройти по нему с интервалом.

Новые блоги и статьи Все статьи Все блоги /
Unity 4D GameUnited 13.06.2025 Четырехмерное пространство. . . Звучит как что-то из научной фантастики, правда? Однако для меня, как разработчика со стажем в игровой индустрии, четвертое измерение давно перестало быть абстракцией из. . .	SSE (Server-Sent Events) в ASP.NET Core и .NET 10 UnmanagedCoder 13.06.2025 Кажется, Microsoft снова подкинула нам интересную фичу в новой версии фреймворка. Работая с превью . NET 10, я наткнулся на нативную поддержку Server-Sent Events (SSE) в ASP. NET Core Minimal APIs. Эта. . .	С днём независимости России! Hrethgir 13.06.2025 Решил побеседовать, с утра праздничного дня, с LM о завоеваниях. То что она написала о народе, представителем которого я являюсь сам сначала возмутило меня, но дальше только смешило. Это чисто. . .	Лето вокруг. kumehtar 13.06.2025 Лето вокруг. Наполненное бурями и ураганами событий. На фоне магии Жизни, священной и вечной, неумелой рукой человека рисуется панорама душевного непокоя. Странные серые краски проникают и. . .	Популярные LM модели ориентированы на увеличение затрат ресурсов пользователями сгенерированного кода (грязь -заслуги чистоплюев). Hrethgir 12.06.2025 Вообще обратил внимание, что они генерируют код (впрочем так-же ориентированы разработчики чипов даже), чтобы пользователь их использующий уходил в тот или иной убыток. Это достаточно опытные модели,. . .
Топ10 библиотек C для квантовых вычислений bytestream 12.06.2025 Квантовые вычисления - это та область, где теория встречается с практикой на границе наших знаний о физике. Пока большая часть шума вокруг квантовых компьютеров крутится вокруг языков высокого уровня. . .	Dispose и Finalize в C# stackOverflow 12.06.2025 Работая с C# больше десяти лет, я снова и снова наблюдаю одну и ту же историю: разработчики наивно полагаются на сборщик мусора, как на волшебную палочку, которая решит все проблемы с памятью. Да,. . .	Повышаем производительность игры на Unity 6 с GPU Resident Drawer GameUnited 11.06.2025 Недавно копался в новых фичах Unity 6 и наткнулся на GPU Resident Drawer - штуку, которая заставила меня присвистнуть от удивления. По сути, это внутренний механизм рендеринга, который автоматически. . .	Множества в Python py-thonny 11.06.2025 В Python существует множество структур данных, но иногда я сталкиваюсь с задачами, где ни списки, ни словари не дают оптимального решения. Часто это происходит, когда мне нужно быстро проверять. . .	Работа с ccache/sccache в рамках C++ Loafer 11.06.2025 Утилиты ccache и sccache занимаются тем, что кешируют промежуточные результаты компиляции, таким образом ускоряя последующие компиляции проекта. Это означает, что если проект будет компилироваться. . .

Опции темы

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

Решение