Задача на расстановку гирь в сумму простых чисел

Условие задачи:

Имеются гири с массами: 1 г, 2 г, …, N г .Требуется написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.

Входные данные Входной файл INPUT.TXT содержит единственное натуральное число N, не превосходящее 500 000.

Выходные данные В выходной файл OUTPUT.TXT выведите список найденных пар. Каждая пара выводится в одной строке через пробел.

Сразу говорю, меня больше интересует идея и доказательство решения, а не код. (вопрос получается скорее математический)

Первое, что навевает на ум - найти наименьшее простое число большее n, к которому мы будем приравнивать наши суммы и выводить. Такое простое число обязательно найдется по постулату Бертрана, т.к. наш диапазон сумм лежит в диапазоне [n + 1; 2n - 1] <=> (n;2n)

1. А может искать простое надо не большее чем n? Искомый диапазон сумм же [3; 2n - 1]. Распространение простых чисел неопределенно и поэтому может возникнуть плохая ситуация.. То есть допустим, у меня есть n, а следующее ближайшее простое n + 4000. И представим, что n - 2 - простое (если вопрос почему не n - 1, то n + 4000 - простое => n + 4000 - нечетное => n - нечетное, n - 1 - четно и имеет делитель 2, n - 2 не имеет подобного делителя). Очевидно, что мне нужно выбрать n - 2 и, благодаря этому выбору, я получу максимальное количество сумм. Или же такая ситуация невозможна? И почему?

2. Вопрос с количеством ответов. На одном из форумов прочитал что количество ответов - n/2 (целочисленной деление), и с этим утверждением я не сильно согласен, но и доказать не сильно смогу. Допустим я дано n и p > n. Тогда мои решения: (p - n + n); (p - n + 1 + n - 1); (p - n + 2 + n - 3) ... и т.д. пока они станут равными или одно слагаемое станет больше другого. Тут получается гарантированно (n - (p - n))/2 <=> (2n - p)/2 <=> n - (p - 1)/2 пар (почленное деление и p - простое, априрори нечетное, значит уменьшаем на 1 чтобы получилось целочисленное деление). Но у нас же остались еще числа 1, 2, 3, 4 ... p - n - 1. Получается исходная задача. Тут есть (p - n)/2 пар То есть, мы доказали для какого то большого случая, что разложение в пары есть. Теперь для меньшего очевидно тоже есть (мат. индукция). Только вот вопрос как добраться до ответа n/2. Если представить, что все оставшиеся числа можно представить в виде суммы простых чисел, то все становится тривиально - 1, 2, 3, 4 ... p - n - 1 имеет (p - n)/2 количество пар. Суммируем с исходными парами (2n - p)/2 + (p - n)/2 <=> (2n - p + p - n)/2 <=> n/2. Однако может быть, что не все числа можно собирать в сумму одного и тоже простое числа. Но мы же доказали для большого случая, что мы можем создавать пары? а значит и этот можем создавать нужные пары. И так бесконечно. Но максимальное количество пар - и есть n/2, значит это по идее и должно являться ответом. Я делаю допущение, что лучший выбор - выбор ближайшего простого после n. Так что доказательство не полное без первого пункта.

в случае непоняток пишите, я дополню и сделаю некоторые вещи поподробнее

сам алгоритм: (acmp зачел как верное, что в какой то степени подтверждает верность 1 пункта, но как доказать его все еще не знаю)

#include <bits/stdc++.h>
using namespace std;

bool check_prime(int n) //проверка простоты
{
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}

int next_prime(int n) //следующее простое число большее n
{
    int next_prime = n + 1 + (n & 1);
    while (!check_prime(next_prime))
        next_prime += 2;
    return next_prime;
}

int main()
{
    int n;
    cin >> n;
    while (n > 1) //пока существуют пары
    {
        int prime = next_prime(n);
        int l; //левая граница
        for (size_t i = 1;; i++)
        {
            if (i + n == prime) //находим границу
            {
                l = i;
                break;
            }
        }
        int cnt = 0;
        for (size_t i = l; i <= (n + l)/2; i++)
        {
            cout << i << " " << n - cnt++ << endl; //выводим пары
        }
        n = l - 1; //решаем случай для чисел 1,2,3 ... l - 1 и решаем до тех пор пока не останется 1 число
    }
}