meh

#include <bits/stdc++.h>
#define F first
#define S second
//#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
const int N = 1e5 + 9;
const int INF = 1e9 + 5;
const int K = 55;

int segTree[N][K], lazy[N][K], A[N], lp[N], last[N], dp[N][K];

void propaGate (int v, int l, int r, int ID) {
    segTree[v][ID] += lazy[v][ID];

    if (l == r) {
        lazy[v][ID] = 0;

        return;
    }

    lazy[2 * v][ID] += lazy[v][ID];
    lazy[2 * v + 1][ID] += lazy[v][ID];

    lazy[v][ID] = 0;
    return;
}

int getQuery (int v, int l, int r, int L, int R, int ID) {
    propaGate (v, l, r, ID);

    if (L <= l && r <= R)
        return segTree[v][ID];

    if (l > R || r < L)
        return 0;


    int mid = (l + r) / 2;
    int Q1 = getQuery (2 * v, l, mid, L, R, ID);
    int Q2 = getQuery (2 * v + 1, mid + 1, r, L, R, ID);

    return max (Q1, Q2);
}

void updateValue (int v, int l, int r, int idx, int val, int ID) {
    propaGate (v, l, r, ID);

    if (l == r) {
        segTree[v][ID] = val;

        return;
    }

    int mid = (l + r) / 2;
    if (idx <= mid)
        updateValue (2 * v, l, mid, idx, val, ID);
    else updateValue (2 * v + 1, mid + 1, r, idx, val, ID);

    segTree[v][ID] = max (segTree[2 * v][ID], segTree[2 * v + 1][ID]);
    return;
}

void updateRange (int v, int l, int r, int L, int R, int ID) {
    propaGate (v, l, r, ID);

    if (L <= l && r <= R) {
        lazy[v][ID]++;
        propaGate (v, l, r, ID);

        return;
    }

    if (l > R || r < L)
        return;

    int mid = (l + r) / 2;
    updateRange (2 * v, l, mid, L, R, ID);
    updateRange (2 * v + 1, mid + 1, r, L, R, ID);

    segTree[v][ID] = max (segTree[2 * v][ID], segTree[2 * v + 1][ID]);
    return;
}

vector <int> F (int x) {
    vector <int> v, tmp;

    while (lp[x] != x) {
        tmp.pb (lp[x]);
        x /= lp[x];
    }

    if (x != 1)
        tmp.pb (lp[x]);

    sort (tmp.begin(), tmp.end());
    for (int i = 0; i < (int) tmp.size(); i++) {
        if (i == 0) {
            v.pb (tmp[i]);

            continue;
        }

        if (tmp[i] != tmp[i - 1])
            v.pb (tmp[i]);
    }

    return v;
}

int main () {
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        cin >> A[i];

    for (int i = 1; i < N; i++)
        lp[i] = i;
    for (int i = 2; i < N; i++)
        if (lp[i] == i)
            for (int j = i + i; j < N; j += i)
                lp[j] = i;


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k + 1; j++) {
            vector <int> v = F (A[i]);
            for (auto u: v) {
                updateRange (1, 1, n, last[u] + 1, i, j - 1);
                last[u] = i;
            }

            dp[i][j] = getQuery (1, 1, n, 1, i - 1, j - 1);
            updateValue (1, 1, n, i, dp[i][j], j);
        }
    }

    cout << dp[n][k + 1] << "\n";

    return 0;
}