A WA Java

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

public class Solution {
    static final int N = 100000001;
    static final int M = 100002;
    static int[] spf = new int[N];
    static int[] lazy = new int[4 * M];
    static int[] tree = new int[4 * M];
    static int[] a = new int[M];

    static void sieve() {
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i < N; ++i) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.add(i);
            }
            for (int j = 0; j < primes.size() && primes.get(j) <= spf[i] && i * primes.get(j) < N; ++j) {
                spf[i * primes.get(j)] = primes.get(j);
            }
        }
    }

    static int isGood(int num) {
        while (num > 1) {
            int p = spf[num];
            int cnt = 0;
            while (num % p == 0) {
                num /= p;
                cnt++;
            }
            if (cnt % 2 == 0)
                return 0;
        }
        return 1;
    }

    static void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = isGood(a[start]);
            return;
        }
        int 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];
    }

    static void propagate(int node, int start, int end) {
        if (lazy[node] == -1)
            return;
        if (lazy[node] == 0)
            tree[node] = 0;
        else
            tree[node] = end - start + 1;
        if (start != end) {
            lazy[2 * node] = lazy[node];
            lazy[2 * node + 1] = lazy[node];
        }
        lazy[node] = -1;
    }

    static void update(int node, int start, int end, int l, int r, int val) {
        propagate(node, start, end);
        if (start > r || end < l)
            return;
        if (start >= l && end <= r) {
            lazy[node] = val;
            propagate(node, start, end);
            return;
        }
        int mid = (start + end) / 2;
        update(2 * node, start, mid, l, r, val);
        update(2 * node + 1, mid + 1, end, l, r, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    static int query(int node, int start, int end, int l, int r) {
        propagate(node, start, end);
        if (start > r || end < l)
            return 0;
        if (start >= l && end <= r)
            return tree[node];
        int mid = (start + end) / 2;
        return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r);
    }

    static void solve(BufferedReader br, PrintWriter out) throws IOException {
        sieve();
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int q = Integer.parseInt(input[1]);
        Arrays.fill(lazy, -1);
        input = br.readLine().split(" ");
        for (int i = 1; i <= n; ++i)
            a[i] = Integer.parseInt(input[i - 1]);
        build(1, 1, n);
        while (q-- > 0) {
            input = br.readLine().split(" ");
            int type = Integer.parseInt(input[0]);
            int l = Integer.parseInt(input[1]);
            int r = Integer.parseInt(input[2]);
            if (type == 2) {
                out.println(query(1, 1, n, l, r));
            } else {
                int x = Integer.parseInt(input[3]);
                update(1, 1, n, l, r, isGood(x));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int tc = 1;
        // tc = Integer.parseInt(br.readLine());
        for (int i = 1; i <= tc; ++i) {
            solve(br, out);
        }
        out.close();
    }
}