La ultima ora de
matematica Gigel a invatat despre numere prime si cum se poate afla daca un
numar este prim sau nu. Dar, asa cum stim deja, lui Gigel ii place sa se joace
cu numerele. Si imediat in mintea lui a aparut o problema: daca numeroteaza
colegii de clasa de la 1 la n,
se pot forma perechi de colegi astfel incat suma numerelor lor de ordine sa
fie un numar prim? Si daca DA, care este numarul maxim de astfel de perechi
care se pot forma?
Cerinta Dat fiind n, numarul de elevi
din clasa, sa se determine toate perechile de elevi care pot fi formate.
Date de intrare Fisierul de intrare perechi.in contine pe prima linie un numar natural nenul n,
reprezentand numarul de elevi din clasa lui Gigel.
Date de iesire Fisierul de iesire perechi.out contine pe fiecare linie cate doua numere naturale separate printr-un spatiu
reprezentand numerele de ordine a doi elevi ce satisfac conditiile problemei.
Restrictii si
precizari 2 <= n <= 100 000
Un elev poate sa apara in cel mult o pereche
Ordinea in care perechile apar in fisierul de iesire este arbitrara
Ordinea in care numerele apar in pereche este arbitrara
Exemplu
perechi.in
perechi.out
Explicatii
7
1
6
5 2
4 7
Perechile
care se pot forma sunt:
1 + 6 = 7 (numar prim)
5 + 2 = 7 (numar prim)
4 + 7 = 11 (numar prim)
Se observa faptul ca 3 nu
apare in nici o pereche; el ar fi putut sa apara in pereche cu 4,
caz in care nu ar fi aparut 7
prof.
Marinel erban
Liceul de Informatica "Gr. C. Moisil" Iasi
marinel_serban@yahoo.com