Tìm số tiền tố (prefix sum) là số nguyên tố trong truy vấn khoảng bằng C++

Cho mảng arr[] và truy vấn L, R. Tạo mảng tiền tố prefixsum[] bắt đầu từ arr[L]: prefixsum[0] = arr[L], prefixsum[i] = prefixsum[i-1] + arr[L+i]. Đếm số phần tử của prefixsum[] là số nguyên tố.

Ví dụ

Input: arr[] = {3, 5, 6, 2, 4}, L=1, R=3 Output: 3
prefixsum: [5, 11, 13] → đều là số nguyên tố

Input: arr[] = {6, 10, 5, 8, 11}, L=0, R=3 Output: 1
prefixsum: [6, 16, 21, 29] → chỉ 29 là nguyên tố

Phương pháp

Xây dựng mảng prefixsum từ L đến R. Dùng Sieve of Eratosthenes kiểm tra nguyên tố cho các giá trị trong prefixsum. Đếm số lượng nguyên tố.

Mã nguồn C++

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

vector<bool> checkprime(int *arr, int n, int MAX) {
    vector<bool> p(n);
    vector<bool> Prime(MAX + 1, true);
    Prime[0] = Prime[1] = false;
    for (int i = 2; i * i <= MAX; i++)
        if (Prime[i])
            for (int j = i * 2; j <= MAX; j += i)
                Prime[j] = false;
    for (int i = 0; i < n; i++)
        p[i] = Prime[arr[i]];
    return p;
}

int main() {
    int arr[] = {2, 3, 4, 7, 9, 10};
    int s1 = sizeof(arr) / sizeof(arr[0]);
    int L = 1, R = 3, s2 = R - L + 1;
    int prefixsum[s2];
    int count = 0;

    prefixsum[0] = arr[L];
    for (int i = L + 1, j = 1; i <= R && j < s1; i++, j++)
        prefixsum[j] = prefixsum[j - 1] + arr[i];

    vector<bool> isprime = checkprime(prefixsum, s2, prefixsum[s2 - 1]);
    for (int i = 0; i < s2; i++)
        if (isprime[i]) count++;

    cout << "Số prefix sum nguyên tố: " << count;
    return 0;
}

Kết quả

Số prefix sum nguyên tố: 2

Giải thích

Tạo mảng prefixsum kích thước R-L+1. Phần tử đầu = arr[L], các phần tử sau cộng dồn. Dùng Sieve tìm nguyên tố lên đến giá trị lớn nhất của prefixsum. Duyệt mảng isprime đếm kết quả.

Kết luận