Untitled

#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define deb(x) cout << #x << "=" << x << "\n"
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << "\n"

const ll mod = 1e9 + 7;
const ll N = 200005;


ll arr[300005],tree[2000009],tree2[2000009];
ll cnt[1000010];
 
void build(ll node, ll l, ll r)
{
    if(l>r)
        return;
    if(l==r)
    {
        tree[node]=arr[l];
        tree2[node]=(tree[node]!=2&&tree[node]!=1);
        return;
    }
    build(node*2,l,(l+r)/2);
    build(node*2+1,(l+r)/2+1,r);
    tree[node]=(tree[node*2]+tree[node*2+1]);
    tree2[node]=tree2[node*2]|tree2[node*2+1];
}

void update(ll node, ll l, ll r,ll i, ll j)
{
    if(i>r||j<l||l>r)
        return;
    if(l==r)
    {
        tree[node]=cnt[tree[node]];
        tree2[node]=(tree[node]!=2&&tree[node]!=1);
        return;
    }
    if(tree2[node*2])
        update(node*2,l,(l+r)/2,i,j);
    if(tree2[node*2+1])
        update(node*2+1,(l+r)/2+1,r,i,j);
    tree[node]=(tree[node*2]+tree[node*2+1]);
    tree2[node]=tree2[node*2]|tree2[node*2+1];
}

ll query(ll node, ll l, ll r, ll i, ll j)
{
    if(i>r||l>j||l>r)
        return 0;
    if(l>=i&&r<=j)
    {
        return tree[node];
    }
    ll left=query(node*2,l,(l+r)/2,i,j);
    ll right=query(node*2+1,(l+r)/2+1,r,i,j);
    return (left+right);
}

void solve()
{
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=1000000;i++)
    {
        for(ll j=i;j<=1000000;j+=i)
        {
            cnt[j]++;
        } 
    }

    for(ll i=1;i<=n;i++)cin>>arr[i];
    build(1,1,n);
    while(m--)
    {
        ll type;
        cin>>type;
        if(type==1)
        {
            ll i,j;
            cin>>i>>j;
            update(1,1,n,i,j);
        }
        else if(type==2)
        {
            ll i,j;
            cin>>i>>j;
            cout<<query(1,1,n,i,j)<<"\n";
        }
    }

}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    IOS;
    ll test_cases = 1;
    // cin >> test_cases;

    while (test_cases--) {
        solve();
    }

    return 0;
}