Нашел первые 4 оптимальных решения, а вот дальше никак не получается. Если не найдешь оптимальное (или близкое к нему) то получаешь очень мало очков.
Проверил жадный алгоритм. Начинаем на всех ребрах по 1. Потом вставляем простые числа по одному в порядке убывания. Выбираем вставление которое дает самую маленькую сумму. Алгоритм работает быстро даже для больших

, но результаты не очень.
-- 30.09.2017, 07:58 --Кстати задачу можно переформулировать с помощью матриц. Найдите

симметричную матрицу

из первых

простых (на главной диагонали все 1) у которой минимальная оценка:

.