rt，紫题显然是恶评。

刚刚因为spoj的输出格式问题，调了半天。但改完还是不对，现在不知道是不是格式的问题了。

代码

#include <iostream>

using namespace std;

const int N = 1000010;
#define int long long

int n, q;
int a[N];
bool vis[N];

struct SegmentTree {
    int l, r;
    int dat, add;
} t[N << 2];

void pre() {
    vis[1] = true;
    for (int i = 2; i <= 1e6; i++) {
        if (vis[i]) continue;
        for (int j = i; j * i <= 1e6; j++) vis[i * j] = true;
    }
    for (int i = 1; i <= 1e6; i++) vis[i] = !vis[i];
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) { t[p].dat = vis[a[l]], t[p].add = 0; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build((p << 1) | 1, mid + 1, r);
    t[p].dat = t[p << 1].dat + t[(p << 1) | 1].dat, t[p].add = 0;
}

void spread(int p) {
    if (t[p].add) {
        t[p << 1].dat = (vis[t[p].add] ? t[p << 1].r -t[p << 1].l + 1 : 0);
        t[(p << 1) | 1].dat = (vis[t[p].add] ? t[(p << 1) | 1].r -t[(p << 1) | 1].l + 1 : 0);
        t[p << 1].add = t[(p << 1) | 1].add = t[p].add;
        t[p].add = 0;
    } 
}

void change(int p, int l, int r, int v) {
    if (l <= t[p].l && r >= t[p].r) {
        t[p].dat = (vis[v] ? t[p].r - t[p].l + 1 : 0);
        t[p].add = v;
        return;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) change(p << 1, l, r, v);
    if (r > mid) change((p << 1) | 1, l, r, v);
    t[p].dat = t[p << 1].dat + t[(p << 1) | 1].dat;
}

int ask(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) return t[p].dat;
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1, val = 0;
    if (l <= mid) val += ask(p << 1, l, r);
    if (r > mid) val += ask((p << 1) | 1, l, r);
    return val;
}

signed main() {
    pre(); int T;
    // cout << vis[3] << " " << vis[13] << " " << vis[15]; 
    scanf("%lld", &T);
    int tot = 0;
    while (T--) {
        printf("Case: %lld\n", ++tot);
        scanf("%lld%lld", &n, &q);
        for (int i = 1; i <= n; i++) scanf("%lld", a + i);
        build(1, 1, n);
        while (q--) {
            int opt, x, y; scanf("%lld%lld%lld", &opt, &x, &y);
            if (opt == 1) printf("%lld\n", ask(1, x, y));
            else {
                int v; scanf("%lld", &v);
                change(1, x, y, v);
            }
        }
    }
    return 0;
}