#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

int LIS(unsigned int ind, vector<int>&a, int gg) {
	if (ind == a.size())return 0;
	int take = 0;
	int ngg = __gcd(gg, a[ind]);
	if (ngg != 1)take = max(LIS(ind + 1, a, ngg) + 1, take);

	int nottake = LIS(ind + 1, a, gg);
	return max(take, nottake);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int n;
	cin >> n;
	vector<int> a(n);

	for (int i = 0; i < n; ++i)cin >> a[i];
	sort(a.begin(), a.end());

	int ans = 0;

	for (int i = 0; i < n; ++i) {
		ans = max(ans, LIS(i, a, 0));
	}

	cout << ans << endl;



	return 0;
}

Obvious TLE.

Could you implement it please, thanks!!!

Won't this TLE? N <= 10^6 and there are roughly 70K primes less than 500000.

void solve()
{

    int n, ans = 0; cin >> n;
    vector<int> a(n);

    for (auto &i : a) cin >> i;
    int mx = *max_element(a.begin(), a.end());

    vector<int> dp(mx + 1, 0);
    for (auto &i : a) dp[i]++;

    for (int i = mx; i >= 1; i--) {

        if (!dp[i]) continue;
        int val = dp[i];

        for (int j = 2 * i; j <= mx; j += i)
            dp[i] = max(dp[i], val + dp[j]);

        ans = max(ans, dp[i]);

    }

    cout << ans << "\n";
}

Won't this be enough?

sir will this work? I have very little knowledge so asking

#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "Templates/printContainer.h"
#endif
#define dbg(x) cout << #x << " = " << x << endl;
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ins insert
#define INF 1000000000
#define pii pair<int,int>
#define EPS 1e-9
#define Endl "\n"
#define fst first
#define snd second
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define sqr(a) (a)*(a)
#define log(b,n) (log2(n)/(log2(b))) //logBase_b_(n)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define _hello cout<<"hello\n";
#define _pow2(k) 1LL<<k
const long long mod=1e9+7;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
using namespace std;
bool _areEqual(double x,double y)
{
    return (abs(x-y)<EPS) ? true : false;
}

string _bin(int decimal)
{
    //prints n bit integer
    int n=8;
    //you can change according to ur need
    string bin;
    for(int i=0;i<n;i++)
    {
        bin.pb(((decimal&(1<<i))>>i)+'0');
    }
    reverse(bin.begin(),bin.end());
    return bin;
}
bool isPrime(ll n)
{
    if(n==2) return true;
    int lim=sqrt(n)+1;
    for(int i=3; i<=lim; i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}

template <typename T> void inputContainer(std::vector<T>& v)       { for(auto &it:v) cin>>it; }
template <typename T> void base1InputContainer(std::vector<T>& v)  { int n=v.size()-1; for(int i=1;i<=n;i++)cin>>v[i]; }
                      void printVector(std::vector<int>& v)        { for(auto it:v)cout<<it<<" "; cout<<endl; }
                      void base1printContainer(std::vector<int>& v){ int n=v.size()-1; for(int i=1;i<=n;i++)cout<<v[i]<<" ";cout<<endl; }
class DSU
{
public:
    vector<int> rank,parent;
    DSU(int n)
    {
        for(int i=0; i<=n; i++)
            rank.pb(0);
        //parent.resize(n);
        for(int i=0; i<=n; i++)
            parent.pb(i);
    }
    int _findParent(int u)
    {
        if(u==parent[u]) return u;
        //else
        return parent[u]=_findParent(parent[u]);
    }
    void _union(int u,int v)
    {
        int pu=parent[u];
        int pv=parent[v];
        if(pu==pv) return;
        //else
        if(rank[pu]<rank[pv])
        {
            parent[pu]=pv;
        }
        else if(rank[pu]>rank[pv])
        {
            parent[pv]=pu;
        }
        else
        {
            parent[pu]=pv;
            ++rank[pv];
        }
    }
};

class edge
{
public:
    int u,v,w;
    edge(int u,int v,int w)
    {
        this->u=u;
        this->v=v;
        this->w=w;
    }
    bool operator<(const edge& other) const
    {
        return w>other.w;
    }

};

int dp[1000000];
int n;
int f(vector<int>& v,int i,int lastTaken)
{
    if(i==-1) return 0;
    if(dp[i]!=-1) return dp[i];
    int takeIt;
    if(v[i]%lastTaken==0)
        takeIt=1+f(v,i-1,v[i]);
    else takeIt=INT_MIN;
    int dontTakeIt=f(v,i-1,lastTaken);
    return dp[i]=max(takeIt,dontTakeIt);
}
void solve()
{
    memset(dp,-1,sizeof(dp));
    cin>>n;
    vector<int> a(n);
    for(auto &it:a)
        cin>>it;
    sort(rall(a));
    cout<<f(a,n-1,1)<<endl;
	//comment out fast_io if I/O related problem occurs
}
int main() {
    fast_io;
    int t = 1;
    cin >> t;
     for (int i = 1; i <= t; i++)
         solve();
}

//graphs -->vector<int> adj[n+1]; n=# of vertices
/*
taking graph input
for(int i=1;i<=n;i++)
{
    cin>>u>>v;
    adj[u].pb(v);
    adj[v].pb(u);//ONLY IF UNDIRECTED GRAPH
}
*/