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.

h4. $Solutia 2.2: O(M * log(log M)) + O(N * NR_MAX_DIV) - 100 puncte$
==user(user="Teodor94" type="tiny")==

h4. $Solutia 2.2: O(M * log(log M)) + O(N * NR_MAX_DIV) - 100 puncte$ ==user(user="Teodor94" type="tiny")==

Vom pregenera numerele prime pana la $sqrt(MAX_VAL)$ folosind Ciurul lui Eratosthenes. Vom descompune in factori primi toate valorile celor $N$ noduri. In continuare, vom genera toti divizorii unui numar cu un algoritm de tip backtraking, folosindu-ne de factorii sai primi si exponentii acestora. Astfel, ajungem din nou la ideea solutiei anterioare, continuand rezolvarea in acelasi fel.