Bài 3. (4 điểm) Tổng nguyên tố Cho một dãy A gồm N số nguyên a1, a2, , aN, một đoạn của dãy A được hiểu là một dãy được tạo thành từ các phần tử liên tiếp của dãy A, chẳng hạn đoạn [u,v] gồm các phần tử au, au+1, , av (1uvN). Với mỗi đoạn [u,v], hãy kiểm tra tổng các phần tử của đoạn có phải là số nguyên tố hay không? Dữ liệu: Vào từ tệp văn bản BAI3.INP gồm: - Dòng đầu tiên chứa 2 số nguyên dương N, M trong đó N là số phần tử của dãy A, M là số đoạn cần kiểm tra. - Dòng thứ 2 chứa N số nguyên dương a1,a2, ,aN (|ai|10000). - M dòng tiếp theo, dòng thứ i chứa hai số nguyên dương u, v tương ứng yêu cầu thứ i kiểm tra au+au+1+ +av có phải là số nguyên tố hay không? Kết quả: Ghi ra tệp văn bản BAI3.OUT trên M dòng, dòng thứ i (1iM) tương ứng với kết quả câu hỏi i, ghi số 1 nếu tổng là số nguyên tố, ngược lại ghi số 0. Ví dụ: BAI3.INP BAI3.OUT Giải thích 5 3 2 7 3 4 6 3 4 3 5 2 4 1 1 0 a3+a4=3+4=7 a3+a4+a5=3+4+6=13 a2+a3+a4=7+3+4=14 Chú ý: - Có 50% số test tương ứng 50% số điểm có N103; M105; - Có 30% số test tương ứng 30% số điểm có N103; M106; - Có 20% số test tương ứng 20% số điểm có N103; M2x106.

`*` Tư tưởng: Ta sử dụng mảng sum (mảng cộng dồn) để lưu trữ tổng. Tức là với mỗi giá trị của sum[i] chứa tổng các phần tử từ `1 -> n`. Vậy tổng từ vị trí `u -> v` là sum[v] - sum[u-1]

Ta kiểm tra xem nó có phải là số nguyên tố hay không

$\texttt{C++}$

#include <bits/stdc++.h>

using namespace std;
bool check(long long n)
{
    if (n < 2)
        return false;
    for (long long i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
int main()
{
    freopen("BAI3.INP", "r", stdin);
    freopen("BAI3.OUT", "w", stdout);
    long long n, m, u, v, res, sum[100005];
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> res;
        sum[i] = sum[i - 1] + res;
    }
    while (m--)
    {
        cin >> u >> v;
        if (check(sum[v] - sum[u - 1]))
        {
            cout << 1 << '\n';
        }
        else
        {
            cout << 0 << '\n';
        }
    }
}

#include <iostream>
#include <math.h>
#define ll long long
using namespace std;
bool prime(ll n){
    for (ll i=2; i<=sqrt(n); i++) if (n%i==0) return false;
    return n>=2;
}
int main() {
    ll n,m;
    cin >> n >> m;
    ll s[n+1],p;
    s[0]=0;
    for (ll i=1; i<=n; i++) cin >> p,s[i]=s[i-1]+p;
    ll a,b;
    while (m--) {
        cin >> a >> b;
        if (prime(s[b]-s[a-1])) cout << 1;
        else cout << 0;
        cout << endl;
    }
}