#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<array>

using namespace std;
typedef long long ll;
int T;
const int M = 5e6 + 200;
const int N = 1e5 + 200;

int tot;
int dfn[M],dep[M],idx[M],ar[N];
ll phi[M],prime[M];
bool is_prime[M];
const ll inf = 0x3f3f3f3f3f3f3f3f;

vector<int>r[M];

void phi_table()
{
  memset(is_prime,true,sizeof is_prime);
  int cnt = 0;
  is_prime[1] = false;
  phi[1] = 1;
  int n = 5e6;
  for(int i = 2;i <= n;i ++)
  {
    if(is_prime[i])
    {
      prime[++ cnt] = i;
      phi[i] = i - 1;
    }
    for(int j = 1;j <= cnt && i * prime[j] <= n;j ++)
    {
      is_prime[i * prime[j]] = false;
      if(i % prime[j])
      {
        phi[i * prime[j]] = phi[i] * phi[prime[j]];
      }
      else
      {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  } 
}

struct node
{
  ll lca,depsum,cnt;
  bool isallone;
}tree[N*4];

int getlca(int x,int y)
{
  if(dep[x] < dep[y]) swap(x,y);

  while(dep[x] > dep[y])
    x = phi[x];

  if(x == y)
  return x;

  while(x != y)
  {
      x = phi[x];
      y = phi[y];
  }
  return x;
}

void dfs(int x)
{
  dfn[x] = ++ tot;
  idx[tot] = x;
  if(x != -1)
    dep[x] = dep[phi[x]] + 1; // 距离1的深度
  else dep[x] = 1;            // 边界
  for(auto v:r[x])
  dfs(v);
}
void update(int x)
{
  tree[x].lca = getlca(tree[x << 1].lca,tree[x << 1 | 1].lca);
  tree[x].depsum = tree[x << 1].depsum + tree[x << 1 | 1].depsum;
  tree[x].cnt = tree[x << 1].cnt + tree[x << 1 | 1].cnt;
  if(tree[x << 1].isallone && tree[x << 1 | 1].isallone)
  tree[x].isallone = true;
}

void build(int l,int r,int x)
{
  if(l == r)
    {
        if(ar[l] == 1)
            tree[x] = {ar[l],dep[ar[l]],1,1};
        else
            tree[x] = {ar[l],dep[ar[l]],1,0};
        return;
    }
    int mid = (l + r)>>1;
    build(l,      mid,x << 1);
    build(mid + 1,r  ,x << 1 | 1);
    update(x);
}

void modify(int l,int r,int x,int L,int R)
{// 当前区间左右边界 当前区间id 修改目标区间左右边界
  if(r < L || l > R) return;
  if(tree[x].isallone) return;

  if(l == r) // 单点修改
  {
    ar[l] == phi[ar[l]];
    if(ar[l] == 1) tree[x] = {ar[l],dep[ar[l]],1,1};//全1
    else tree[x] = {ar[l],dep[ar[l]],1,0};
    return;
  }
  int mid = l+r>>1;
  modify(l,     mid,x << 1    ,L,R);
  modify(mid + 1,r, x << 1 | 1,L,R);
  update(x);
}

array<ll,3> query(int l,int r,int x,int L,int R)
{// 当前索引到的查询区间左右端点 索引号 查询目标左右边界
  if(L <= l && R >= r)
  return {tree[x].lca,tree[x].depsum,tree[x].cnt};
  int mid = l+r>>1;
  if(R <= mid) return query(l,mid,x << 1,L,R);
  else
  {
    if(L > mid) return query(mid + 1,r,x << 1|1,L,R);
  else{
  array<ll,3>tp1 = query(l,mid,x << 1,L,mid);
  array<ll,3>tp2 = query(mid+1,r,x << 1|1,mid + 1,R);
  return {getlca(tp1[0],tp2[0]),tp1[1] + tp2[1],tp1[2] + tp2[2]};
  }
  }
}

void solve()
{
   int n,m;
   cin >> n >> m;
   phi_table();
   for(int i = 2;i <= 5e6;i ++)
   r[phi[i]].push_back(i);
   dfs(1);
   for(int i = 1;i <= n;i ++)
   cin >> ar[i];
   build(1,n,1);
   while(m --)
   {
    int opr,l,r;
    cin >> opr >> l >> r;
    if(opr == 2)
    {
      array<ll,3>res = query(1,n,1,l,r);
      ll ans = res[1] - res[2]*(dep[res[0]]*1ll);
      cout << ans << endl;
    }
    else modify(1,n,1,l,r);
   }
}

int main()
{
  //scanf("%d",&T);
  T = 1;
  while(T--)
      solve();
}

#include<bits/stdc++.h>
using namespace std;
#define MX 5000000 + 200
#define N 100000 + 200
int tot;
int dfn[MX],dep[MX],idx[MX],ar[N];
long long phi[MX],prime[MX];
bool is_prime[MX];
const long long inf = 0x3f3f3f3f3f3f3f3f;
vector<int>r[MX];
void phi_table() 
{
    memset(is_prime, 1, sizeof(is_prime));
    int cnt = 0;
    is_prime[1] = 0;
    phi[1] = 1;
    int n = 5000000;
    for (int i = 2; i <= n; i++) 
    {
        if (is_prime[i]) 
        {
            prime[++ cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) 
        {
            is_prime[i * prime[j]] = 0;
            if (i % prime[j])
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            else 
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}
struct node
{
    long long lca,depsum,cnt;
    bool isallone;

}tree[4 * N];
int getlca(int x,int y)
{
    if(dep[x] < dep[y])
        swap(x,y);
    while(dep[x] > dep[y])
        x = phi[x];
    if(x == y)
        return x;
    while(x != y)
        x = phi[x],y = phi[y];
    return x;
}
void dfs(int x)
{
    dfn[x] = ++ tot;
    idx[tot] = x;
    if(x != 1)
        dep[x] = dep[phi[x]] + 1;
    else
        dep[x] = 1;
    for(auto v:r[x])
        dfs(v);
}
void update(int x)
{
    tree[x].lca = getlca(tree[2 * x].lca,tree[2 * x + 1].lca);
    tree[x].depsum = tree[2 * x].depsum + tree[2 * x + 1].depsum;
    tree[x].cnt = tree[2 * x].cnt + tree[2 * x + 1].cnt;
    if(tree[2 * x].isallone && tree[2 * x + 1].isallone)
        tree[x].isallone = 1;
}
void build(int l,int r,int x)
{
    if(l == r)
    {
        if(ar[l] == 1)
            tree[x] = {ar[l],dep[ar[l]],1,1};
        else
            tree[x] = {ar[l],dep[ar[l]],1,0};
        return;
    }
    int mid = (l + r) / 2;
    build(l,mid,2 * x),build(mid + 1,r,2 * x + 1);
    update(x);
}
void modify(int l,int r,int x,int L,int R)
{
    if(r < L || l > R)
        return;
    if(tree[x].isallone)
        return;
    if(l == r)
    {
        ar[l] = phi[ar[l]];
        if(ar[l] == 1)
            tree[x] = {ar[l],dep[ar[l]],1,1};
        else
            tree[x] = {ar[l],dep[ar[l]],1,0};
        return;
    }
    int mid = (l + r) / 2;
    modify(l,mid,2 * x,L,R),modify(mid + 1,r,2 * x + 1,L,R);
    update(x);
}
array<long long,3>query(int l,int r,int x,int L,int R)
{
    if(L <= l && R >= r)
        return {tree[x].lca,tree[x].depsum,tree[x].cnt};
    int mid = (l + r) / 2;

    if(R <= mid)
        return query(l,mid,2 * x,L,R);
    else
    {
        if(L > mid)
            return query(mid + 1,r,2 * x + 1,L,R);
        else
        {
            array<long long,3>tmp1 = query(l,mid,2 * x,L,mid);
            array<long long,3>tmp2 = query(mid + 1,r,2 * x + 1,mid + 1,R);
            return {getlca(tmp1[0],tmp2[0]),tmp1[1] + tmp2[1],tmp1[2] + tmp2[2]};
        }
    }
}
int main()
{

    int n,m;
    scanf("%d %d",&n,&m);
    phi_table();
    for(int i = 2;i <= 5000000;i ++)
        r[phi[i]].push_back(i);
    dfs(1);
    for(int i= 1;i <= n;i ++)
        scanf("%d",&ar[i]);
    build(1,n,1);

    for(int i = 1;i <= m;i ++)
    {

        int opr,l,r;
        scanf("%d %d %d",&opr,&l,&r);
        if(opr == 2)
        {
            array<long long,3>res = query(1,n,1,l,r);
            long long ans = res[1] - res[2] * (dep[res[0]] * 1ll);
            printf("%lld\n",ans);
        }
        else
            modify(1,n,1,l,r);

    }

}