const LL mod = 1000000007;
const int maxn = 200005;
int n,m,k;
int a[maxn],dp[maxn];
int vis[maxn],vv[maxn];
vector<int > vc[maxn],vs[maxn];
int ans;

void bfs(int u){
    vv[u] = 1;
    int z = a[u];
    int len = vc[z].size();
    for(int i = 0;i<len;i++){
        int v = vc[z][i];
        int le = vs[v].size();
        for(int j = 0;j<le;j++){
            int b = vs[v][j];
            if(vv[b] == 0){
                ans++;
                bfs(b);
            }
        }
    }
}


int main()
{
    cin>>n;
    for(int i = 0;i<n;i++){
        int x;
        scanf("%d",&a[i]);
        x = a[i];
        if(vis[x] == 1) {
            int le = vc[x].size();
            for(int j=0;j<le;j++){
                int v = vc[x][j];
                vs[v].push_back(i);
            }
            continue;
        }
        vis[x] = 1;
        int y = x;
        for(int j =2;j*j<=y;j++){
            if(y%j==0){
                vc[x].push_back(j);
                while(y%j==0){
                    y/=j;
                }
            }
        }
        if(y!=1) vc[x].push_back(y);
        int len = vc[x].size();
        for(int j=0;j<len;j++){
            int v = vc[x][j];
            vs[v].push_back(i);
        }
    }

    int ll = vs[2].size();
    int maxx = 0;
    for(int i = 0;i<n;i++){
        if(vv[i] == 0){
            ans = 1;
            bfs(i);
            maxx = max(ans,maxx);
        }
    }
    cout<<maxx<<endl;
    return 0;
}