OBM 1998 3° fase

Acho que eu consegui fazer:vamos "fingir" que dá para formar os 15 com fatores primos de modo que tomando um par (a,b) qualquer mdc(a,b)=1 e a e b não são primos.

Vamos supor que cada número seja o quadrado de um primo.
a1=2²
a2=3²
a3=5²
.....
an=Pn² -----> onde Pn é o enésimo primo

Bom, perceba que teremos uma quantidade limitada de primos para usar pois o conjunto está entre 1 e 1998, veja:
43²=1849
47²=2209
como 47²>1998------> só poderemos usar os primos até 43, ou seja:
2,3,5,7,11,13,17,19,23,29,31,37,41,43 (14 números). No entanto queremos 15 números primos entre sí e não primos, o que é impossível visto que temos só 14 primos disponíveis para elevarmos ao quadrado. Logo um dos números deve ser primo assim poderiamos colocar por ex o conjunto 2²,3²,5²,7²,11²,13²,17²,23²,29²,31²,37²,41²,43²,47