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

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

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

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

@bormant · 15.11.2018, 13:00

Pascal

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 и дальше пройти по нему с интервалом.

Опции темы

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

Решение