#include <cstdio>#include <cstring>#include <queue>#include <set>#include <vector>#include <cmath>#include <map>#include <stack>#include <algorithm>using namespace std ;#define LL __int64#define INF 0x3f3f3f3f#define PI acos(-1.0)#define root 1,n,1#define int_rt int l,int r,int rt#define lson l,(l+r)/2,rt<<1#define rson (l+r)/2+1,r,rt<<1|1const int mod = 1e9+7 ;const double eqs = 1e-9 ;int cl[400000] , num[400000] ;int a[10000005] , check[10000005] ;int tot ;void init() { memset(check,-1,sizeof(check)) ; tot = 0 ; for(int i = 2 ; i <= 10000000 ; i++) { if( check[i] == -1 ){ a[tot++] = i ; check[i] = 1 ; } for(int j = 0 ; j < tot ; j++) { if( i*a[j] >= 10000000 ) break ; check[i*a[j]] = 0 ; if( i%a[j] == 0 ) break ; } } check[0] = check[1] = check[6] = 1 ; for(int i = 2 ; i <= 10000000 ; i *= 2) check[i] = 1 ;}void push_up(int rt) { cl[rt] = max(cl[rt<<1],cl[rt<<1|1]) ; num[rt] = num[rt<<1]+num[rt<<1|1] ;}void create(int_rt) { cl[rt] = num[rt] = 0 ; if( l == r ) { scanf("%d", &cl[rt]) ; if( check[ cl[rt] ] == 1 ) num[rt] = 1 ; return ; } create(lson) ; create(rson) ; push_up(rt) ;}void update1(int ll,int rr,int v,int_rt) { if( ll > r || rr < l ) return ; if( cl[rt] < v ) return ; if( l == r ) { cl[rt] %= v ; if( check[ cl[rt] ] == 1 ) num[rt] = 1 ; else num[rt] = 0 ; return ; } update1(ll,rr,v,lson) ; update1(ll,rr,v,rson) ; push_up(rt) ;}void update2(int k,int x,int_rt) { if( l == r && l == k ) { cl[rt] = x ; if( check[ cl[rt] ] == 1 ) num[rt] = 1 ; else num[rt] = 0 ; return ; } int mid = (l+r)/2 ; if(k <= mid) update2(k,x,lson) ; else update2(k,x,rson) ; push_up(rt) ;}int query(int ll,int rr,int_rt) { if( ll > r || rr < l ) return 0 ; if( ll <= l && rr >= r ) return num[rt] ; return query(ll,rr,lson) + query(ll,rr,rson) ;}int main() { int n , m , i , k , l , r , v , x ; init() ; while( scanf("%d", &n) !=EOF ) { create(root) ; scanf("%d", &m) ; while( m-- ) { scanf("%d", &k) ; if( k == 1 ) { scanf("%d %d", &l, &r) ; printf("%dn", query(l,r,root)) ; } else if( k == 2 ) { scanf("%d %d %d", &l, &r, &v) ; update1(l,r,v,root) ; } else { scanf("%d %d", &i, &x) ; update2(i,x,root) ; } } } return 0 ;}
