Distrugere

distrugere

Considerăm un şir format din $N$ numere naturale. Definim operaţia _distrugere-X_ astfel:
* se alege un număr natural $X$ care apare în şir;

* se şterg toate numerele din şir care au cel puţin un divizor comun cu $X$ mai mare decât 1.
 
Operaţia _distrugere-X_ se aplică o singură dată.
h2. Cerinţă
 
Scrieţi un program care, cunoscând $N$ şi elementele şirului, determină numărul maxim de elemente care pot să rămână în şir după aplicarea unei singure operaţii _distrugere-X_.

* se şterg toate numerele din şir care au cel puţin un divizor comun cu $X$ mai mare decât 1.

h2. Date de intrare

Fişierul de intrare $distrugere.in$ conţine pe prima linie numărul natural $N$, cu semnificaţia din enunţ. Pe cea de-a doua linie se află $N$ numere naturale separate prin câte un spaţiu, reprezentând elementele şirului.

Fişierul de intrare $distrugere.in$ ...

h2. Date de ieşire

Fişierul de ieşire $distrugere.out$ conţine o singură linie pe care este scris numărul maxim de elemente care pot rămâne în şir după aplicarea unei singure operaţii _distrugere-X_.

În fişierul de ieşire $distrugere.out$ ...

h2. Restricţii şi precizări

h2. Restricţii

* $2 ≤ N ≤ 200 000$
* $1 ≤ elementele şirului ≤ 1 000 000$
 
|_. # |_. Punctaj |_. Restricţii |
| $1$ | $14$ | $2 ≤ N ≤ 1 000$ |
| $2$ | $36$ | $1 001 ≤ N ≤ 50 000$ |
| $3$ | $50$ | Fără restricţii suplimentare |

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. distrugere.in |_. distrugere.out |

| 4
15 2 6 9
| 2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Există 4 variante de alegere a valorii $X$:
 
* $X$ = 15: se elimină 6, 9, 15 şi rămâne 1 element (2).
* $X$ = 2: se elimină 2, 6 şi rămân 2 elemente (9, 15);
* $X$ = 6: se elimină 2, 6, 9, 15 şi rămân 0 elemente;
* $X$ = 9: se elimină 6, 9, 15 şi rămâne 1 element (2);
 
Numărul maxim de elemente rămase este 2.

...

== include(page="template/taskfooter" task_id="distrugere") ==