GGSPAG

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
#define MAX 100001
long segtree[4*MAX];
bool primes[MAX],input[MAX];
//use the sieve to store all the primes till MAX.
//primes are marked as zero.
void sieve()
{
  memset(primes,1,sizeof(primes));
  for(int i=2;i<sqrt(MAX);i++)
  {
    if(!primes[i]) continue;
      for(int j=i*2;j<MAX;j+=i)
        primes[j]=0;
  }
  primes[1]=0;

}

//build the segemnt tree
void build(int node,int st,int en)
{
  if(st==en)
  {
    segtree[node]=input[st];
    return;
  }
  int mid=(st+en)/2;

  build(node*2,st,mid);
  build(node*2+1,mid+1,en);
  segtree[node]=segtree[node*2]+segtree[node*2+1];

}

//update the segment tree (point update)
void update(int node,int st,int en,int index)
{
  if(index>en || index<st)
    return;
  if(st==en && st==index)
  {
    segtree[node]=input[index];
    return;
  }
  int mid=(st+en)/2;
  update(node*2,st,mid,index);
  update(node*2+1,mid+1,en,index);
  segtree[node]=segtree[node*2]+segtree[node*2+1];
}

//query the segment tree for prime numbers.
long query(int node,int st,int en,int qs,int qe)
{
  //cout<<"Q("<<node<<" "<<st<<" "<<en<<")"<<endl;
  if(qs > en || qe < st)//completely outside
   return 0;
  if(qs <= st && qe >= en)//completely inside
    return segtree[node];
int mid=(st+en)/2;
  return query(node*2,st,mid,qs,qe)+ query(node*2+1,mid+1,en,qs,qe);

}

int main()
{
  sieve();

  long n,q;
  long long num,j=0;
  cin>>n>>q;

  for(int i=1;i<=n;i++)
  {
    scanf("%d",&num);
    (primes[num]) ? input[i]=1 : input[i]=0;


  }
  build(1,1,n);
  long type,X,Y;
  while(q--)
  {
    cin>>type>>X>>Y;
    if(type==1)//query
    {

        cout<<query(1,1,n,X,Y)<<endl;
    }
    else
    {
      (primes[Y])? input[X]=1 : input[X]=0;
        update(1,1,n,X);
    }
  }


}