Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010

#define MAXA 1000010

bool isprime[MAXA];

int prime[MAXA],tot = 0;

int sigma[MAXA],cnt[MAXA],mindivs[MAXA];

void sieve()

{

	for(int i = 2;i < MAXA;++i)isprime[i] = true;

	cnt[1] = 1;sigma[1] = 1;mindivs[1] = 1;

	for(int i = 2;i < MAXA;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			cnt[i] = 1;

			sigma[i] = 2;

			mindivs[i] = i;

		}

		for(int j = 1;j <= tot && i * prime[j] < MAXA;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)

			{

				mindivs[i * prime[j]] = mindivs[i] * prime[j];

				cnt[i * prime[j]] = cnt[i] + 1;

				sigma[i * prime[j]] = sigma[i / mindivs[i]] * (cnt[i * prime[j]] + 1);

				break;

			}

			else

			{

				mindivs[i * prime[j]] = prime[j];

				cnt[i * prime[j]] = 1;

				sigma[i * prime[j]] = sigma[i] * 2;

			}

		}

	}

	return;

}

int a[MAXN];

struct node

{

	int lc,rc;

	long long sum;

	bool tag;

	node(){lc = rc = 0;sum = 0ll;tag = false;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void pushup(int rt)

{

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	if(t[t[rt].lc].tag && t[t[rt].rc].tag)t[rt].tag = true;

	return;

}

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].sum = (long long)a[l];

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	pushup(rt);

	return;

}

void change(int rt,int L,int R,int l,int r)

{

	if(t[rt].tag)return;

	if(l == r)

	{

		t[rt].sum = sigma[t[rt].sum];

		if(t[rt].sum == 1 || t[rt].sum == 2)t[rt].tag = true;

		return;

	}

	if(L <= mid)change(t[rt].lc,L,R,l,mid);

	if(R >= mid + 1)change(t[rt].rc,L,R,mid + 1,r);

	pushup(rt);

	return;

}

long long query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)

	{

		return t[rt].sum;

	}

	long long res = 0;

	if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

	if(R >= mid + 1)res += query(t[rt].rc,L,R,mid + 1,r);

	return res;

}

int main()

{

	sieve();

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

		scanf("%d",&a[i]);

	build(root,1,n);

	int x,y,z;

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

	{

		scanf("%d%d%d",&x,&y,&z);

		if(x == 1)

		{

			change(root,y,z,1,n);

		}

		else

		{

			cout << query(root,y,z,1,n) << endl;

		}

	}

	return 0;

}