题目只要求子序列，没有要求连续，直接暴力枚举质因子即可

Java 代码

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        /*
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        */
        Scanner scanner = new Scanner(System.in);
        final int N = 100010;
        int[] arr = new int[N], p = new int[N];

        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) arr[i] = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            // prime factorization
            List<Integer> prime = new ArrayList<>();
            int cur = arr[i];
            for (int j = 2; j <= Math.sqrt(cur); j++) {
                if (cur % j == 0) {
                    prime.add(j);
                    while (cur % j == 0) cur /= j;
                }
            }
            if (cur > 1) prime.add(cur);
            int max = 0;
            for (int x : prime) {
                max = Math.max(max, p[x]);
            }
            for (int x : prime) {
                p[x] = max + 1;
            }
        }
        int res = 1;
        for (int i = 0; i < N; i++) res = Math.max(res, p[i]);
        System.out.println(res);

        /*
        bw.flush();
        bw.close();
        br.close();
        */
    }
}