Vom considera ca cele $N$ numere sunt nodurile unui graf neorientat, iar fiecare nod $i$ o sa aiba valoarea $a[i]$. Initial, graful are $N$ noduri si $0$ muchii. Pentru fiecare nod $i$ de la $1$ la $N$, vom parcurge toate celelalte $N$ noduri, iar cand gasim un nod $j$ care are proprietatea ca $a[i]$ divide $a[j]$ sau viceversa, vom trage o muchie intre aceste doua noduri $i$ si $j$. In momentul acesta, problema se reduce la gasirea numarului de componente conexe existente in acest graf. Acest lucru se poate face liniar cu o parcurgere in adancime / latime.

h4. $Solutia 2.1: O(N * sqrt( MAX_VAL )) - 70 puncte$ ==user(user="Teodor94" type="tiny")==

h4. $Solutia 2.1: O(N * sqrt( MAX_VAL )) - 70 puncte$

Pe acelasi principiu ca cel al rezolvarii anterioare, putem adauga valoarea tuturor nodurilor intr-o tabela de dispersie / hash, retinand pentru fiecare valoare $a[i]$ adaugata, numarul de ordine al nodului careia ii apartine, si anume $i$. In continuare vom parcurge valorile tuturor celor $N$ noduri si le vom cauta divizorii in hash. Daca gasim un divizor in hash, vom trage muchie intre nodul curent si nodul din hash care are valoarea divizorului gasit. In acest moment, problema se reduce din nou la gasirea numarului de componente conexe ale grafului.