提供一种不是很聪明的思路。（求轻喷）

思路

感觉这个思路有点像 dp。首先把 $10^5$ 之间的素数都筛出来了（init_()），用 $p_i$ 表示这里面第 $i$ 个素数。然后扫描题目给的 $n$ 个数，在每一次扫描的时候维护一个数组 $dp$，$dp[i]$ 表示在当前扫描位置之前，满足以下条件的最长子序列的长度：

• 子序列的最后一个元素含有质因子 $p_i$。

这样我们就可以状态转移。比如扫描到第 $i$ 个数 $a_i$，它含有质因子 $p_{i1},p_{i2},\cdots,p_{it}$。也就是说这个数可以接在谁后面呢，任何一个序列，只要这个序列的最后一个数含有上面 $t$ 个因子的任何一个，那么 $a_i$ 就可以接在这个序列后面。我们记
$$mx=\max(dp[i1],dp[i2],\cdots,dp[it])$$

那么在这一次扫描中，我们需要将 $dp[i1],dp[i2],\cdots,dp[it]$ 的值更新为 $mx+1$。重复扫描到尾部，在 $dp$ 数组中取最大值即可。

时间复杂度

由于 $\pi(n)\sim\cfrac{n}{\log n}$，所以时间复杂度为 $O(n^2/\log n)$

C++ 代码

上文 $p_i$ 对应下面的 pr[i]，$dp[i]$ 对应下面的 cnt[i]。

# include <iostream>
# include <cstring>
# include <vector> 
# include <cstring>

using namespace std;

const int N = 1e5 + 3;
int n,a,ans;
int pr[100005],cnt[100005],pos;
bool test[100005];
int temp_arr[100005],temp_pos;

void init_(){
    memset(test,true,sizeof(test));
    for(int i = 2;i <= N;i++){
        if(test[i])
            for(int j = 2;i * j <= N;j++)
                test[i * j] = false;
    }
    for(int i = 2;i <= N;i++)
        if(test[i])
            pr[pos++] = i;
}

int main(){
    int mx,res = 0;
    cin >> n;
    init_();
    for(int i = 1;i <= n;i++){
        scanf("%d",&a);
        if(a == 1) {res = 1;continue;}
        temp_pos = mx = 0;
        for(int j = 0;pr[j] <= a;j++){
            if(a % pr[j] == 0){
                temp_arr[temp_pos++] = j;
                mx = max(mx,cnt[j]);
                while(a % pr[j] == 0) a /= pr[j];
            }
        }
        mx++;
        for(int i = 0;i < temp_pos;i++)
            cnt[temp_arr[i]] = mx;
    }
    for(int i = 0;i <= N;i++)
        res = max(res,cnt[i]);
    return cout << res,0;
}