https://codeforces.com/problemset/problem/920/F

题解：

线性筛+线段树+因子个数

先用素数线性筛筛选出因子个数

线段树维护

参考文章：https://blog.csdn.net/weixin_43272781/article/details/85058735

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=300000+10;
const int M=1000000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
int D[M];
int pre[M];
bool prime[M];
ll tree[N<<2];
bool skip[N<<2];
void pushup(int rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
    skip[rt]=skip[rt<<1]&&skip[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        scanf("%d",&tree[rt]);
        if(tree[rt]<=2)
            skip[rt]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);

}
void updata(int l,int r,int rt,int L,int R){
    if(skip[rt])
        return;
    //cout<<rt;
    if(l==r){
        tree[rt]=D[tree[rt]];
        if(tree[rt]<=2)
            skip[rt]=1;
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)updata(l,mid,rt<<1,L,R);
    if(R>mid)updata(mid+1,r,rt<<1|1,L,R);
    pushup(rt);
}
ll query(int l,int r,int rt,int L,int R){
    if(l>=L&&r<=R){
        return tree[rt];
    }
    int mid=(l+r)>>1;
    ll res=0;
    if(L<=mid)res+=query(l,mid,rt<<1,L,R);
    if(R>mid)res+=query(mid+1,r,rt<<1|1,L,R);
    return res;
}
char str;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif

    D[1]=1;
    prime[0]=prime[1]=1;
    for(int i=2;i<M;i++){
        if(!prime[i]){
            D[i]=2;
            pre[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*pre[j]<M;j++){
            prime[i*pre[j]]=1;
            D[i*pre[j]]=D[i]*2;
            if(i%pre[j]==0){
                int c=1;
                t=i;
                while(t%pre[j]==0){
                    t/=pre[j];
                    c++;
                }
                D[i*pre[j]]=D[t]*(c+1);
                break;
            }
        }
        //cout<<i<<" "<<D[i]<<endl;
    }
    scanf("%d%d",&n,&m);
    build(1,n,1);
    int l,r;
    while(m--){
        scanf("%d%d%d",&t,&l,&r);
        if(t==1){
            updata(1,n,1,l,r);
        }else{
            cout<<query(1,n,1,l,r)<<endl;
        }
    }


    //cout << "Hello world!" << endl;
    return 0;
}