数论练习题

#include<bits/stdc++.h>
using namespace std;
#define IT set<int>::iterator
#define pii pair<int,int>
#define LL long long
#define pb push_back
#define F(i,a,b) for(int i=a;i<=b;i++)
#define dF(i,b,a) for(int i=b;i>=a;i--)
const int N = 1e5+5;
int f[N],a[N],n;
int main()
{
    cin>>n;
    F(i,1,n)
    {
        int x,maxn = 0;
        cin>>x;
        int t = x;
        for(int j = 2;j*j<=x;j++)
            if(x % j == 0)
            {
                maxn = max(maxn,f[j]+1);
                maxn = max(maxn,f[t/j]+1);
                while(x % j == 0) x /= j;
            }
        if(x > 1) maxn = max(maxn,f[x]+1);
        x = t;
        if(x > 1) f[x] = maxn;
        for(int j = 2;j*j<=x;j++)
            if(x % j == 0)
            {
                f[j] = maxn;
                f[x/j] = maxn;
            }
    }
    int ans = 1;
    for(int i = 1;i<=1e5;i++) ans = max(ans,f[i]);
    cout << ans << '\n';
    return 0;
}