Hello everybody,

Today was the practice session of CEOI 2016 and the following interesting problem was given:

You're given N distinct integers. Print the maximum sum you can get by adding two of them that are coprime.

N is up to 100,000 and all the numbers are between 1 and 500,000. Time limit is 1 second, memory limit is 256MB.

Some solutions passed but most of them were using some odd tricks with unclear complexity. I was wondering if some neat solutions exist?