Как из первых N натуральных чисел составить максимальное количество пар, суммы которых являются простыми?

Question

[leean]

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

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

Выходные данные
В выходной файл OUTPUT.TXT выведите список найденных пар. Каждая пара выводится в одной строке через пробел.
Я написал код задачи, и не понимаю почему на каком-то тесте он выдаёт не правильный ответ, хотя я не допускал ошибок, я знаю как можно решить по другому и за меньшее время, но мне интересно какой же тест не проходит это решение:

#include<bits/stdc++.h>

using namespace std;

bool check(int n){
    int i,j;
    for(i=2;i<=sqrt(n);++i){
        if(n%i==0){
            return false;
        }
    }
    return true;


}


int main(){
ifstream cin("input.txt");
ofstream cout("output.txt");

int n;
cin>>n;
if(n==1){
    return 0;
}
vector<int>a(n+1);
a.clear();
for(int i=0;i<=n;++i){
    a[i]=i;
}

for(int i=n;i>=0;i--){
    if(a[i]!=0){
        for(int j=0;j<=n;j++){
            bool f;
            if(a[j]!=0&&a[i]!=0&&i!=j){
            int temp;
            temp=i+j;

            f=check(temp);
                if(f==true){
                    cout<<i<<" "<<j<<endl;
                    a[i]=0;
                    a[j]=0;
                }
            }
        }
    }
}

return 0;

}

Comments

[Rsa97]

Для начала, приведите точную формулировку задачи, а не своё изложение.

[kalapanga]

Только что хотел то же самое написать. Не приведены требования по вводу-выводу данных, не приведены никакие ограничения, саму задачу в такой формулировке можно понять минимум двумя разными способами.
Никогда не пересказывайте задачу своими словами - только дословное воспроизведение.

[leean]

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

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

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

[Wexter]

https://freelance.habr.com/

[Владислав Лысков]

Не уместно

[leean]

Владислав Лысков, +

[mayton2019]

Хотел спросить по заданию.

Правильный ли input-output я написал?

2 => [{1 2}]

3 => [{1 2}, {2 3}]

Может ли гиря участвовать несколько раз в парах?

Нужен ли порядок гирь в паре (сочетания/размещения) ?

Answer 1

[Wataru]

В вашем решении есть ошибки: Вы считаете сумму двух чисел от 0 до N, а не от 1 до N.

А главная проблема вашего решения в том, что оно "жадное". Вы жадно берете первую папавшуюся пару, как будто так будет оптимально. Но это не так. Например, если у вас остались гири весами 2, 3, 4, 5, то брать пару 2+3 = 5 нельзя, ведь тогда оставшиеся 4+5=9 дадут не простое число.

Это действительно можно решать через задачу о паросочетании как сказал Alexandroppolus. Вот только все алгоритмы работают за O(N^3), так что для N=500000 это решение будет работь очень долго.

Но в вашем случае граф очень специфичный, так что надо придумать какой-то шаблон. Например, можно взять максимальное простое число P <= N+1 и набирать его всеми возможными парами (1+(P-1), 2+(P-2)). В итоге у вас остнется одна нечетная гиря (P+1)/2 и все гири >=P. Например, если N+1 простое - то это оптимальный способ.

Я бы посоветовал написать решение через максимальное паросочетание и прогнать его для всех N <=200. Получите оптимальные ответы, посмотрите на них. Поищите какой-то паттерн в количестве пар, потом попробуйте придумать способ такое количество набрать.

И еще немного покритикую ваш код.
f==true. Зачем? Можно написать if(f). А вообще вам тут f не нужно, пишите if(Check(i+j)).

Вместо

if(a[j]!=0&&a[i]!=0&&i!=j) { 
  ...
}

стоит использовать "ранний выход":

if(!a[i] || !a[j] || i == j) continue; 
...

Так вложенность и сложность кода меньше. Его проще читать и понимать.

Вместо прверки, что i != j, можно внутренний цикл гнать от n до i+1. Вам же не надо перебирать отдельно пары 1+10 и 10+1? Всегда считайте, что первое число меньше второго в паре.

Ну, и отступы, ради всего святого, расставьте аккуратно. Любой редактор кода умеет их делать автоматически.

Edit:
Совместо с Alexandroppolus в комментариях придумали следующее решение: Берете минимальное простое число, большее N. Обзовем его P. Тогда берем пары N+(P-N), (N-1)+(P-N+1)... и т.д. В этих парах одно число четное, другое нечетное. И всего они покроют отрезок четной длины без дырок. Потом задача сводится к такой же, только уже с максимальным числом не N, а P-N-1.
Эта жадность работает, потому что она всегда соберет максимально теоретически возможное количетсво пар. Может только одна 1 в конце останется.

Comments

[Alexandroppolus]

Например, можно взять максимальное простое число P <= N+1 и набирать его всеми возможными парами (1+(P-1), 2+(P-2)). В итоге у вас остнется одна нечетная гиря (P+1)/2 и все гири >=P. Например, если N+1 простое - то это оптимальный способ.

тоже подумал об этом способе.

"осевое" простое число P можно брать и больше N+1. Тогда, наоборот, остаётся набор маленьких гирь, а все большие задействуются. Ну и гиря (P+1)/2. Или её не будет оставаться? Кажется, не будет.
Соответственно из оставшихся пробуем аналогично составлять пары, выбрав другое "осевое" P

видимо, перебирать надо вот такие варианты выбора "осевых" простых чисел.

[Alexandroppolus]

Ну и гиря (P+1)/2. Или её не будет оставаться? Кажется, не будет.

да, гири (P+1)/2 при этом не остается. Только ровненький набор гирек 1,2,3,...,K, для которого решаем ту же задачу. Выглядит как ДП.

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

[Wataru]

Alexandroppolus, Да, похоже, так и надо. Только это не ДП, а умная жадность. Мы так доказали, что можно все floor(n/2) пар составить. Тут какая-то теорема о том, что среди K..2K обязательно есть простое число нужна (не помню, как она называется), чтобы доказать, что минимальное простое число, большее N будет меньше 2N. А значит можно всегда взять и откусить какие-то максимальные гири.

[Alexandroppolus]

Wataru,

Тут какая-то теорема о том, что среди K..2K обязательно есть простое число нужна (не помню, как она называется

постулат Бертрана.

[Alexandroppolus]

Итого, вместе с Решетом Эратосфена, можно всё дело обстряпать за O(n*ln(ln(n))). Или даже линейно, есть там линейное решето.

[Rsa97]

Сделал несколько по другому.
Берём правую границу r = N для чётных N и r = N - 1 для нечётных N.
Ищем минимальную нечётную левую границу l, такую, что l + r простое число.
Получаем набор пар (l, r), (l + 1, r - 1), ..., (l + (r - l - 1) / 2, r - (r - l - 1) / 2).
Берём новую правую границу r = l - 1.
Повторяем, пока r > 0.
Для N до 50000 получается не более трёх интервалов, всегда полностью закрывающих диапазон.
Например
(25, 49966), (5, 24), (1, 4)

Answer 2

[Alexandroppolus]

Для начала можно построить таблицу простых чисел от 1 до 2N, например с помощью решета Эратосфена. Теперь ты сможешь проверять, что число (или, например, сумма двух чисел) простое, за O(1), то есть быстро.

Далее, как известно, простое число больше 2 всегда нечетное, т.е. оно есть сумма четного и нечетного. Соответственно, все четные числа - в одну кучку, нечетные - в другую. И в каждую пару брать из разных кучек. Вот так и получается, что у тебя тут двудольный граф, в котором числа - вершины, и есть ребро, если сумма двух вершин простая. Задача называется вроде бы "о максимальном паросочетании" или что-то вроде того.

Comments

[Alexandroppolus]

собственно, вот-с: https://e-maxx.ru/algo/kuhn_matching

правда, меня тут смущает, что у него асимптотика O(nm), причем в нашем случае n - до 500000, а m - порядка n/ln(n). Итого O(n^2 / ln(n)). Это, черт возьми, дохренища..

Похоже, надо ещё как-то оптимизировать

Answer 3

[Adamos]

Подозреваю элементарное: под конец цикла остаются два числа, которые при сложении дают не простое, но больше их комбинировать не с чем. Задача-то переборная, а тут один проход без возвратов.

Comments

[leean]

не, последние тоже выводят правильно, перед выводом стоит проверка на простоту, не может просто вывести не правильно, если число остаётся в массиве то оно и не нужно, по условию при вводе 1 ответ ничего, просто не выводить, поэтому все что не нужно не трогает даже

[Adamos]

leean, то, что у вас осталось в массиве, может при других комбинациях войти в максимально возможное число пар, как требуется в задаче.

Answer 4

[Rsa97]

Ключевые слова - максимально возможное количество пар. Значит простой перебор тут не работает, поскольку можно упереться в локальный оптимум и не найти глобального. Нужно перебрать все возможные комбинации пар и найти ту, где простых чисел больше всего.
Пример: при поиске наивным способом для N = 8 получим три пары с простой суммой (1, 2), (3, 4), (5, 6). Оставшаяся пара (7, 8) даст 15, что не является простым числом. Однако, при разбиении (1, 2), (3, 4), (5, 8), (6, 7) получим уже четыре пары с простой суммой.

Comments

[leean]

в моем решении выводит 4 пары...... вы его хотя бы запустите

[Rsa97]

leean, Это для 8 у вас находит все четыре пары. Вы уверены, что ваш алгоритм находит максимальное количество пар для 30? А для 100? А для 50000?

[leean]

Rsa97, да, я проверил

[Wataru]

Для 500000 гирек полный перебор займет вечность.

[Rsa97]

leean, Ну вот, для 26 ваш алгоритм находит 12 пар, а максимальное количество - 13.
Результат вашего алгоритма: (26, 3), (25, 4), (24, 5), (23, 6), (22, 1), (21, 2), (20, 9), (19, 10), (18, 11), (17, 12), (16, 7), (15, 8). Остались 13 и 14.
Вариант с 13 парами: (1, 2), (3, 26), (4, 25), (5, 24), (6, 23), (7, 22), (8, 21), (9, 20), (10, 19), (11, 18), (12, 17), (13, 16), (14, 15).