`*` Sàng `+` Mảng cộng dồn

$\texttt{C++}$

#include <bits/stdc++.h>

using namespace std;
const int nmax = 1e7 + 5;

bool f[nmax+1];
void sangnt() {
    memset(f,true,sizeof(f));
    f[0] = false;
    f[1] = false;
    for(int i = 2; i * i <= nmax; ++i) {
         if(f[i] == true) {
             for(int j = i * i; j <= nmax; j += i)
                 f[j] = false;
        }
    }
}

int main()
{
    freopen("PRIME.INP","r",stdin);
    freopen("PRIME.OUT","w",stdout);
    sangnt();
    int n,m,u,v,res;
    cin>>n>>m;
    vector<int> d(n+1,0);
    for(int i=1;i<=n;i++)
    {
        cin>>res;
        d[i]=d[i-1]+f[res];
    }
    while(m--)
    {
        cin>>u>>v;
        cout<<d[v]-d[u-1]<<endl;
    }
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
bool kt(int num) {
    if (num <= 1)
        return false;
    for (int i = 2; i * i <= num; ++i)
        if (num % i == 0)
            return false;
    return true;
}
int a[1000000];
main() {
    freopen("PRIME.INP", "r", stdin);
    freopen("PRIME.OUT", "w", stdout);
    int n, m;
    cin>>n>>m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    vector<int> k(n+1,0);
    for (int i = 1; i <= n; ++i) {
        k[i] = k[i - 1] + (kt(a[i]) ? 1 : 0);
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin>>u>>v;
        int d = k[v] - k[u-1];
        cout << d << "\n";
    }

    return 0;
}