Условие задачи:
Имеются гири с массами: 1 г, 2 г, …, N г .Требуется написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.
Входные данные Входной файл INPUT.TXT содержит единственное натуральное число N, не превосходящее 500 000.
Выходные данные В выходной файл OUTPUT.TXT выведите список найденных пар. Каждая пара выводится в одной строке через пробел.
Сразу говорю, меня больше интересует идея и доказательство решения, а не код. (вопрос получается скорее математический)
Первое, что навевает на ум - найти наименьшее простое число большее n
, к которому мы будем приравнивать наши суммы и выводить. Такое простое число обязательно найдется по постулату Бертрана, т.к. наш диапазон сумм лежит в диапазоне [n + 1; 2n - 1] <=> (n;2n)
А может искать простое надо не большее чем
n
? Искомый диапазон сумм же[3; 2n - 1]
. Распространение простых чисел неопределенно и поэтому может возникнуть плохая ситуация.. То есть допустим, у меня естьn
, а следующее ближайшее простоеn + 4000
. И представим, чтоn - 2
- простое (если вопрос почему неn - 1
, тоn + 4000
- простое =>n + 4000
- нечетное =>n
- нечетное,n - 1
- четно и имеет делитель2
,n - 2
не имеет подобного делителя). Очевидно, что мне нужно выбратьn - 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 число
}
}