Đếm mảng con có tổng là số nguyên tố trong C++

Cho mảng số nguyên dương. Đếm mảng con có tổng là số nguyên tố. Ví dụ {1,2,3,4} → {1,2}, {2,3}, {3,4} (tổng 3, 5, 7).

Ví dụ

Đầu vào: arr[] = {1,3,5,3,2}
Đầu ra: 3 ({3,2}=5, {3,5,3}=11, {3,5,3,2}=13).

Đầu vào: arr[] = {2,4,6}
Đầu ra: 0.

Giải thuật

• Sử dụng sàng Eratosthenes tìm tất cả số nguyên tố ≤ 10⁷, lưu trong vector<bool> check.
• Duyệt 2 vòng lặp tạo mảng con arr[i..j], tính tổng, kiểm tra check[sum].

Ví dụ triển khai

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

int sub_prime(int arr[], int size) {
    int count = 0;
    int temp = pow(10, 7);
    vector<bool> check(temp + 1, true);
    check[0] = check[1] = false;
    for (int i = 2; i * i <= temp; i++) {
        if (check[i]) {
            for (int j = i * 2; j <= temp; j += i) check[j] = false;
        }
    }
    for (int i = 0; i < size - 1; ++i) {
        int total = arr[i];
        for (int j = i + 1; j < size; ++j) {
            total += arr[j];
            if (check[total]) ++count;
        }
    }
    return count;
}

int main() {
    int arr[] = {3, 5, 1, 9, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of subarrays with Prime sum are: " << sub_prime(arr, size);
    return 0;
}

Kết quả

Count of subarrays with Prime sum are: 1