#include<iostream>
using namespace std;
long long a[300005],tree[1200005];
bool ok[1200005];
int d[1000005];
inline void pushup(int i)
{
	tree[i]=tree[i<<1]+tree[i<<1|1];
	if(ok[i<<1]&&ok[i<<1|1])
	{
		ok[i]=true;
	}
	else
	{
		ok[i]=false;
	}
}
void build(int l,int r,int i)
{
	if(l==r)
	{
		tree[i]=a[l];
		if(a[l]==1||a[l]==2)
		{
			ok[i]=true;
		}
		else
		{
			ok[i]=false;
		}
	}
	else
	{
		int mid=(l+r)>>1;
		build(l,mid,i<<1);
		build(mid+1,r,i<<1|1);
		pushup(i);
	}
}
void modify(int l,int r,int ql,int qr,int i)
{
	if(qr<l||r<ql||ok[i])
	{
		return;
	}
	if(l==r)
	{
		tree[i]=d[tree[i]];
		if(tree[i]==1||tree[i]==2)
		{
			ok[i]=true;
		}
		else
		{
			ok[i]=false;
		}
		return;
	}
	int mid=(l+r)>>1;
	modify(l,mid,ql,qr,i<<1);
	modify(mid+1,r,ql,qr,i<<1|1);
	pushup(i);
}
long long ask(int l,int r,int ql,int qr,int i)
{
	if(qr<l||r<ql)
	{
		return 0;
	}
	if(ql<=l&&r<=qr)
	{
		return tree[i];
	}
	int mid=(l+r)>>1;
	return ask(l,mid,ql,qr,i<<1)+ask(mid+1,r,ql,qr,i<<1|1);
}
int main()
{
	for(int i=1;i<=1000000;i++)
	{
		for(int j=i;j<=1000000;j+=i)
		{
			d[j]++;
		}
	}
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,n,1);
	while(m--)
	{
		int opt,l,r;
		cin>>opt>>l>>r;
		if(opt==1)
		{
			modify(1,n,l,r,1);
		}
		else
		{
			cout<<ask(1,n,l,r,1)<<endl;
		}
	}
	return 0;
}

TLE on #67

是复杂度错了还是常数太大被卡了？