Простые гири (3 уровень)

Условие:
Имеются гири с массами: 1 г, 2 г, ..., N г (N<=500000). Написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.

Технические требования:
Входной файл INPUT.TXT содержит число N. Входные данные корректны. В выходной файл OUTPUT.TXT выводится список найденных пар. Все числа в выходном файле разделяются пробелами и (или) символами перевода строки.

Пример файлов входных и выходных данных:

Время тестирования 20 секунд на каждый тест.

Решение: (by HellMan [alexec@polarcom.ru])

{$A-,B-,D+,E-,F-,G-,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V-,X-,Y+}
{$M 16384,0,655360}

program Giri;

var
  n, i, m, l: longint;

function easy(const n: longint): boolean;
var
  i: longint;
begin
  easy := true;
  for i := 2 to trunc(sqrt(n)) do
  if n mod i = 0 then begin
    easy := false;
    break;
  end;
end;

function findeasy(const n: longint): longint;
var
  i: longint;
begin
  findeasy := 0;
  for i := n + 1 to 999999 do
  if easy(i) then begin
    findeasy := i;
    break;
  end;
end;

begin
  assign(input, 'input.txt');
  reset(input);
  readln(n);
  close(input);

  assign(output, 'output.txt');
  rewrite(output);
  if n = 2 then
  writeln('1 2')
  else if easy(n) then
  for i := n - 1 downto (n + 1) div 2 do
  writeln(i, ' ', n - i)
  else
  begin
    while n > 0 do
    begin
      m := findeasy(n);
      if (m = 0) or (m >= 2 * n) then
      break;
      for i := m - n to m div 2 do
      writeln(i, ' ', m - i);
      n := m - n - 1;
    end;
  end;
  close(output);
end.