Дистанционный практикум по программированию

Имеются гири с массами: 1 г, 2 г, ..., N г (N <= 500000). Написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.
Входные данные:
Входной файл input.txt содержит число N.
Выходные данные
В выходном файле output.txt выводится список найденных пар. Все числа в выходном файле разделяются пробелами и (или) символами перевода строки.
input
7
output
1 6
7 4
5 2