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: 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")==

Timp preprocesare: *$O(M * log(log M))*, unde M este sqrt(MAX_VAL);$
Timp executie: *$O(N * NR_MAX_DIV),* unde NR_MAX_DIV este numarul maxim de divizori al unui numar.$

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.

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.

Complexitatea preprocesarii numerelor prime este $O(M * log(log M))$, unde $M$ este $sqrt(MAX_VAL)$, iar complexitatea efectiva a problemei este $O(N * NR_MAX_DIV)$, unde $NR_MAX_DIV$ este numarul maxim de divizori al unui numar.

h4. $Solutia 3.1: 80 puncte$