#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define ls now<<1
#define rs now<<1|1
#define QwQ puts("QwQ")
using namespace std;
const int N=100005,M=5000005;
int n,m,a[N],phi[M],fa[M][5],dep[M],mx;
struct node
{
	int sum,mx,lca;
}tree[N<<2];
inline int read()
{
	int ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		ans=(ans<<3)+(ans<<1)+(c^48);
		c=getchar();
	}
	return ans*f;
}
inline void write(int x)
{
    if(x<0)
    {
        printf("-"),write(-x);
        return;
    }
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int solve(int x,int y)
{
	if(dep[x]>=dep[y]) swap(x,y);
	for(int i=4;i>=0;i--)
	{
		if(dep[fa[y][i]]>=dep[x]) y=fa[y][i];
	}
	if(x==y) return x;
	for(int i=4;i>=0;i--)
	{
		if(dep[fa[x][i]]!=dep[fa[y][i]]) x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}
void pushup(int now)
{
	tree[now].sum=tree[ls].sum+tree[rs].sum;
	tree[now].mx=max(tree[ls].mx,tree[rs].mx);
	tree[now].lca=solve(tree[ls].lca,tree[rs].lca);
	return;
}
void build(int now,int l,int r)
{
	if(l==r)
	{
		tree[now]={dep[a[l]],dep[a[l]],a[l]};
		return;
	}
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(now);
	return;
}
void update(int now,int l,int r,int ql,int qr)
{
	if(!tree[now].mx) return;
	if(l==r)
	{
		a[l]=phi[a[l]];
		tree[now]={dep[a[l]],dep[a[l]],a[l]};
		return;
	}
	int mid=l+r>>1;
	if(ql<=mid) update(ls,l,mid,ql,qr);
	if(qr>mid) update(rs,mid+1,r,ql,qr);
	pushup(now);
	return;
}
node query(int now,int l,int r,int ql,int qr)
{
	if(l>=ql&&r<=qr) return tree[now];
	int mid=l+r>>1;
	if(qr<=mid) return query(ls,l,mid,ql,qr);
	if(ql>mid) return query(rs,mid+1,r,ql,qr);
	node res,res_ls=query(ls,l,mid,ql,qr),res_rs=query(rs,mid+1,r,ql,qr);
	res.sum=res_ls.sum+res_rs.sum;
	res.mx=max(res_ls.mx,res_rs.mx);
	res.lca=solve(res_ls.lca,res_rs.lca);
	return res;
}
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		mx=max(mx,a[i]);
	}
    for(int i=1;i<=M-5;i++) phi[i]=i;
    for(int i=2;i<=M-5;i++)
    {
    	if(phi[i]==i)
    	{
    		for(int j=i;j<=M-5;j+=i)
    		{
    			phi[j]*=(i-1);
    			phi[j]/=i;
			}
		}
	}
	fa[1][0]=1;
	for(int i=2;i<=M-5;i++) fa[i][0]=phi[i],dep[i]=dep[phi[i]]+1;
	for(int j=1;j<=4;j++)
	{
		for(int i=1;i<=M-5;i++)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	build(1,1,n);
	while(m--)
	{
		int op,l,r;
		op=read(),l=read(),r=read();
		if(op==1) update(1,1,n,l,r);
		else
		{
			node ans=query(1,1,n,l,r);
			write(ans.sum-(r-l+1)*dep[ans.lca]);
			printf("\n");
		}
	}
	return 0;
}