Intr-o zi, a atribuit un numar natural distinct de la $2$ la $M$ celor $N$ vaci ale sale. S-a gandit sa grupeze vacile, bazandu-se pe numerele de pe ele, intr-un numar minim de turme. Totusi, a stabilit urmatoarele conditii, care trebuie satisfacute pentru toate turmele:
* Fie $x$ cel mai mic numar atribuit vacilor dintr-o turma. Fiecare vaca din aceeasi turma trebuie sa aiba un numar de forma $x * k$, unde $k$ este un numar natural.

* Toti divizorii primi ai lui $k$ (in afara de 1) trebuie sa fie mai mari sau egali cu orice divizor prim al lui $x$ pentru toate vacile din turma.

* Toti divizorii lui $k$ (in afara de 1) trebuie sa fie mai mari sau egali cu orice divizor al lui $x$ pentru toate vacile din turma.

Totusi, Tygyn este putin ocupat cu mentinerea pacii pe teritoriul sau, asa ca l-a rugat pe Manchaary sa aiba grija de vaci. Aceasta sarcina parea destul de dificila pentru Manchaary, dar recompensa era minunata: putea sa se casatoreasca cu frumoasa Sardaana!

h3. Tutorial

Puteti vedea o solutie in $O(N + M)$ la 'editorial':tygyn/solutie_romana

Puteti vedea o solutie in $O(N + M)$ la 'editorial':tygyn/solutie

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