GGSPAGtester

#include <iostream>
#define ll long int
using namespace std;
ll a[100002], tree[400004];
bool isComposite[100002];  //will be initialized to false
void build(ll node, ll start, ll end) {
    if(start == end) {
        if(!isComposite[a[start]])
            tree[node] = 1;
        else
            tree[node] = 0;
    } else {
        ll mid = (start + end) / 2;
        build(2*node, start, mid);
        build(2*node+1, mid+1, end);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}
void update(ll node, ll start, ll end, ll idx, ll val) {
    if(start == end) {
        a[idx] = val;
        tree[node] = (isComposite[val])?0:1;
    } else {
        ll mid = (start + end) / 2;
        if(idx <= mid) {
            update(2*node, start, mid, idx, val);
        } else {
            update(2*node+1, mid+1, end, idx, val);
        }
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}
ll query(ll node, ll start, ll end, ll l, ll r) {
    if(r < start || l > end) {
        return 0;
    }
    if(l <= start && r >= end) {
        return tree[node];
    }
    ll mid = (start + end) / 2;
    return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r);
}
int main() {

    //seive's
    isComposite[1] = true;
    for(ll i = 2; i < 100001; i++) {
        if(!isComposite[i]){     //if isPrime
            for(ll j = 2*i; j < 100001; j += i) {
                isComposite[j] = true;
            }
        }
    }

    ll n, q;
    cin>>n>>q;
    for(ll i = 1; i <= n; i++) {
        cin>>a[i];
    }
    build(1, 1, n);
    ll c, l, r;
    while (q--) {
        cin>>c>>l>>r;
        if(c == 1) {
            cout<<query(1, 1, n, l, r)<<"\n";
        } else {
            update(1, 1, n, l, r);
        }
    }
    return 0;
}