简单题。
我们令 $f_i$ 表示 $i$ 结尾的最大长度，$ans=max\ f_i$考虑转移。
我们考虑可以转移向 $i$ 的 $j$，要满足 $gcd(a_i,a_j)>1$，这是个比较经典的问题，等价于两数质因数分解有交集，那么分解一下 $i$ 然后看是那个质因数有交即可，我们记 $g_x$ 为包含 $x$ 这个质因数的 $f_i$ 的最大值，那么 $f_i=max{\ g_{prime}}+1$。
