В вашем решении есть ошибки: Вы считаете сумму двух чисел от 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 в конце останется.
