Để 1 số là số nguyên tố toàn diện cần 3 điều kiện:

      `1.` Bản thân nó là số nguyên tố

      `2.` Bỏ dần chữ số bên phải, phần còn lại vẫn luôn là số nguyên tố

      `3.` Thêm `1` chữ số `(0 - 9)` vào bên phải x, số thu được vẫn là số nguyên tố

`" "`

Bước 1: Nhận xét về chữ số cuối

      `-` Số nguyên tố > `10` thì chỉ có thể chữ số cuối là `1, 3, 7, 9`

      `-` Nếu chữ số cuối là `0, 2, 4, 6, 8` `->` Chia hết cho `2`, không phải nguyên tố

      `-` Nếu chữ số cuối là `5` `->` Chia hết cho `5`, không phải nguyên tố 

`" "`

Bước 2: Suy ra dạng số của x

`-` Từ điều kiện `2`, xóa dần chữ số bên phải thì số còn lại luôn là nguyên tố

`-` Suy ra, bất kì số nào còn từ `2` chữ số trở lên phải kết thúc bằng `1, 3, 7, 9`

`-` Suy ra, mọi chữ số trừ chữ số đầu tiên chỉ có thể là `1, 3, 7, 9`

`-` Sau khi xóa hết tất cả số, còn lại `1` chữ số đầu tiên, nó cũng chỉ có thể là `2, 3, 5, 7` (các chữ số nguyên tố)

`" "`

Bước 3: Sinh các số thay vì kiểm tra từng số

`-` Thay vì duyệt từng số rồi kiểm tra, chỉ sinh số chắc chắn thỏa mãn các điều kiện

`-` Với `4` số ban đầu: `2, 3, 5, 7` `->` Tự động thỏa mãn điều kiện `1, 2`

`-` Với mỗi số hiện có, nối thêm vào bên phải, thử với các trường hợp số là `1, 3, 7, 9`

`-` Số mới là nguyên tố thì giữ lại và tiếp tục sinh từ số này

`-` Lặp lại cho tới khi số vượt quá `1.000.000 `

`" "`

Bước 4: Kiểm tra điều kiện 3

`-` Mọi số sinh thỏa mãn điều kiện `1, 2`

`-` Nối thử `1` chữ số vào bên phải, số mới chỉ có thể là nguyên tố nếu nối `1, 3, 7, 9`

`-` Vì vậy chỉ cần thử với `1, 3, 7, 9, 1` trong `4` trường hợp thỏa mãn điều kiện thì lưu lại là số nguyên tố toàn diện

`" "`

Bước 5: Dùng kết quả để trả lời truy vấn nhanh

`-` Duyệt từng phần tử `a[i]` trong mảng `A`, kiểm tra `a[i]` có nằm trong danh sách số nguyên tố toàn diện hay không

`-` Tính prefix sum theo vị trí: vị trí i, s[i] = số lượng phần tử `a[1], a[2], ..., a[i]` là số nguyên tố toàn diện

`-` Đếm số phần tử nguyên tố toàn diện từ u đến v, chỉ cần tính hiệu `s[v] - s[u - 1]`

`" "`

`C++`

`" "`

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

int n, m, a[N + 1], s[N + 1];
bool st[N + 1];

bool nt(int x) {
    if (x < 2) return false;

    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;

    return true;
}

void dfs(int x) {
    int d[4] = {1, 3, 7, 9};

    for (int i = 0; i < 4; i++)
        if (nt(x * 10 + d[i])) {
            st[x] = true;
            break;
        }

    for (int i = 0; i < 4; i++) {
        int y = x * 10 + d[i];

        if (y <= N && nt(y))
            dfs(y);
    }
}

void nhap() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];

        s[i] = s[i - 1];

        if (st[a[i]])
            s[i]++;
    }

    cin >> m;
}

void xuly() {
    while (m--) {
        int l, r;
        cin >> l >> r;

        cout << s[r] - s[l - 1] << endl;
    }
}

int main() {
    dfs(2);
    dfs(3);
    dfs(5);
    dfs(7);

    nhap();
    xuly();

    return 0;
}