#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef pair<ld, ld> pdd;
#define vec vector
#define For(i, a, n) for(ll i=(ll)a;i<n;i++)
#define all(x) begin(x), end(x)
#define sz(x) (ll)size(x)

template<class A, class B>
pair<A,B>operator+(const pair<A, B>&a, const pair<A,B>&b){
    return {a.first + b.first, a.second + b.second};
}
template<class A, class B>
ostream&operator<<(ostream&os, const pair<A, B>&c){
    return os<<"("<<c.first<<", "<<c.second<<")";
}
template<class A, class B, class C>
basic_ostream<A,B>&operator<<(basic_ostream<A, B>&os, const C&c){
    for(auto itr=begin(c);itr!=end(c);++itr){
        os<<(itr==begin(c)?"":" ")<<*itr;
    }
    return os;
}
template<typename...Args>
void dbg(Args&&...args){
    ((cerr<<args<<" |"),...);cerr<<endl;
}
ll operacie = 0;

const int LIM = 1000000;
bitset<LIM>isPrime;
vec<int> PP;
vec<int> er(){
    const int S = (int) round(sqrt(LIM)), R=LIM/2;
    vec<int> pr={2}, sieve(S+1); pr.reserve(int(LIM/log(LIM)*1.1));
    vec<pll> cp;
    for(int i=3;i<=S;i+=2)if(!sieve[i]){
        cp.push_back({i, i*i/2});
        for(int j=i*i;j<=S;j+=2*i)sieve[j]=1;
    }
    for(int L=1;L<=R;L+=S){
        array<bool, 1000>block{};
        for(auto&[p, idx]:cp){
            for(int i=idx;i<S+L;idx=(i+=p))block[i-L]=1;
        }
        For(i, 0, min(S, R-L)){
            if(!block[i])pr.push_back((L+i)*2+1);
        }
    }
    for(int i:pr)isPrime[i] = 1;
    return pr;
}
vec<ll> primes(ll x)
{
    vec<ll> ans;
    for(auto i : PP){
        if(i>sqrt(x)){
            ans.push_back(x);
            break;
        }
        if(x == 1)break;
        operacie++;
        if (x%i == 0) ans.push_back(i);
        while(x%i == 0) x/= i;
    }
    return ans;
}

ll count1(vec<ll>&p, vec<ll> &primes){
    // dbg(primes, p);
    ll sum = 0, k = 1;
    For(i, 0, 1 << sz(primes))
    {
        ll t = 1;
        k = -1;
        For(j, 0, sz(primes)) if(i & (1 << j))
        {
            t *= primes[j];
            k *= -1;
        }
        if(t == 1) continue;
        p[t] -= 1;
        sum += k*p[t];
        // dbg(t, k);
    }
    // dbg(sum);
    return sum;
}

ll count2(vec<ll> &p, vec<ll> &primes)
{
    // dbg(primes, p);
    ll sum = 0, k = 1;
    For(i, 0, 1 << sz(primes))
    {
        ll t = 1;
        k = -1;
        For(j, 0, sz(primes)) if(i & (1 << j))
        {
            t *= primes[j];
            k *= -1;
        }
        if(t == 1) continue;
        sum += k*p[t];
        p[t] += 1;
        // dbg(t, k);
    }
    // dbg(sum);
    return sum;
}

void solve(){
    PP = er();
    // dbg("mam primes", sz(PP));
    ll n, k, res = 0;
    cin >> n >> k;
    vec<ll> v(n);
    for(ll &x : v) cin >> x;

    ll l = 0, r = 0, t  = 0;
    vec<ll> p(723456, 0);
    while(1) // 2n
    {
        if(t < k){
            if(r+1 > n) break;
            auto pr = primes(v[r++]); // rychlo (10)
            t += count2(p, pr);
            if (t >= k) res+=n-r+1;
        }
        else {
            auto pr = primes(v[l++]);
            t -= count1(p, pr);
            if (t >= k) res+=n-r+1;
        }
    }
    dbg(operacie);
    cout << res << '\n';

}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int t = 1;
    while(t--)solve();
    return 0;
}