A- TLE java

import java.util.*;
import java.io.*;

public class Solution {
    static Map<Long, Boolean> dp = new HashMap<>();

    static boolean good(long n) {
        if (dp.containsKey(n)) return dp.get(n);
        long save = n;
        for (long i = 2; i * i <= n; i++) {
            int cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            if (cnt > 1) {
                dp.put(save, false);
                return false;
            }
        }
        if (n > 1) {
            // The number itself is prime, so it has one prime factor with exponent 1
            // This is still considered "good"
        }
        dp.put(save, true);
        return true;
    }

    static class SegmentTree {
        int size;
        long[] tree;

        SegmentTree(int n) {
            size = 1;
            while (size < n) size *= 2;
            tree = new long[2 * size];
        }

        void build(List<Long> a) {
            build(a, 0, 0, size);
        }

        void build(List<Long> a, int x, int lx, int rx) {
            if (rx - lx == 1) {
                if (lx < a.size()) {
                    tree[x] = a.get(lx);
                }
                return;
            }
            int m = (lx + rx) / 2;
            build(a, 2 * x + 1, lx, m);
            build(a, 2 * x + 2, m, rx);
            tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
        }

        void update(int l, int r, long v) {
            update(l, r, v, 0, 0, size);
        }

        void update(int l, int r, long v, int x, int lx, int rx) {
            if (lx >= r || l >= rx) return;
            if (lx >= l && rx <= r) {
                tree[x] = v * (rx - lx);
                return;
            }
            int m = (lx + rx) / 2;
            update(l, r, v, 2 * x + 1, lx, m);
            update(l, r, v, 2 * x + 2, m, rx);
            tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
        }

        long sum(int l, int r) {
            return sum(l, r, 0, 0, size);
        }

        long sum(int l, int r, int x, int lx, int rx) {
            if (lx >= r || l >= rx) return 0;
            if (lx >= l && rx <= r) return tree[x];
            int m = (lx + rx) / 2;
            return sum(l, r, 2 * x + 1, lx, m) + sum(l, r, 2 * x + 2, m, rx);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        List<Long> a = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            long x = Long.parseLong(st.nextToken());
            a.add(good(x) ? 1L : 0L);
        }

        SegmentTree seg = new SegmentTree(n);
        seg.build(a);

        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken()) - 1;
            int r = Integer.parseInt(st.nextToken());
            if (type == 2) {
                out.println(seg.sum(l, r));
            } else {
                long x = Long.parseLong(st.nextToken());
                seg.update(l, r, good(x) ? 1 : 0);
            }
        }

        out.close();
    }
}