My code Tle's for this problem but I am sure about the complexity. Here's my code --

#include "bits/stdc++.h"
using namespace std;
#define lli long long
#define gc getchar_unlocked
#define MAX 10000001
bool vv[MAX];
int len, sp[MAX];
int dp[MAX];
map<int, map<lli,lli> >  dpsum;
vector<pair<lli, lli> > v[4*MAX];

void scanint(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
void Sieve(){
    for (int i = 2; i < MAX; i += 2) sp[i] = 2;//even numbers have smallest prime factor 2
    for (lli i = 3; i < MAX; i += 2){
    if (!vv[i]){
    sp[i] = i;
    for (lli j = i; (j*i) < MAX; j += 2){
    if (!vv[j*i]) vv[j*i] = true, sp[j*i] = i;
    }
    }
    }
}

void build(int node, int l, int r)
{
    if(l > r)return;
    for(int i = l; i <= r; i++)
    {
        v[node].push_back(make_pair((lli)dp[i], (lli)i));
    }
    sort(v[node].begin(), v[node].end());
    dpsum[node][0] = v[node][0].second*v[node][0].first;
    for(int i = 1; i < v[node].size(); i++)
    {
        dpsum[node][i] = dpsum[node][i-1] + v[node][i].first*v[node][i].second;
    }
    if(l==r)return;
    build(node*2, l, (l+r)/2);
    build(node*2+1, (l+r)/2+1, r);
}

lli query(int node, int L, int R, int l, int r, int k)
{
    if(l > R || r < L || L > R)return 0;
    if(L >= l && R <= r)
    {
        int idx = lower_bound(v[node].begin(), v[node].end(), make_pair((lli)k+1,(lli)0)) - v[node].begin();
        lli sum = 0;
        int tt = v[node].size()-1;
        sum = dpsum[node][tt] - dpsum[node][idx-1];
        return sum;
    }
    lli aa = query(node*2, L, (L+R)/2, l, r, k);
    lli bb = query(node*2+1, (L+R)/2+1, R, l, r, k);
    return (aa+bb);
}

int main()
{
    Sieve();
    
    int n, q;
    
    scanint(n);
    scanint(q);
    
    int a[n+1];
    for(int i = 1; i <= n; i++)
        scanint(a[i]);
        
    map<int, int> ss;
    
    for(int i = 1; i <= n; i++)
    {
        int temp = a[i];
        while(temp > 1)
        {
            if(ss[sp[temp]] == 0){
            dp[i] += sp[temp];ss[sp[temp]]=1;}
            temp = temp/sp[temp];
        }
        ss.clear();
    }
    
    build(1, 1, n);
    while(q--)
    {
        int l, r, k;
        scanint(l);scanint(r);scanint(k);
        printf("%lld\n",query(1, 1, n, l, r, k));
    }
    return 0;
}