นับ Subarray ที่มีผลรวมเป็นจำนวนเฉพาะใน C++

เราได้รับอาร์เรย์จำนวนเต็มบวก เป้าหมายคือหา subarray ที่ผลรวมเป็นจำนวนเฉพาะ (Prime)

ตัวอย่าง

อินพุต: arr[] = {1, 3, 5, 3, 2}

เอาต์พุต: 3

คำอธิบาย: {3,2} sum=5, {3,5,3} sum=11, {3,5,3,2} sum=13

อินพุต: arr[] = {2, 4, 6}

เอาต์พุต: 0

คำอธิบาย: ทุก subarray มีผลรวมไม่ใช่จำนวนเฉพาะ

แนวทางการแก้ปัญหา

1. ใช้ Sieve of Eratosthenes หาจำนวนเฉพาะทั้งหมดถึง 10⁷ เก็บใน vector<bool> check
2. วนลูป 2 ชั้น สร้าง subarray ทุกคู่ คำนวณผลรวม
3. ตรวจสอบ check[sum] ถ้าเป็น true (prime) ให้นับเพิ่ม

การนำไปใช้ (Implementation)

#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;
    
    // Sieve of Eratosthenes
    for (int i = 2; i * i <= temp; i++) {
        if (check[i]) {
            for (int j = i * 2; j <= temp; j += i) {
                check[j] = false;
            }
        }
    }
    
    // นับ subarray ที่ผลรวมเป็นเฉพาะ
    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;
}

เอาต์พุต

Count of subarrays with Prime sum are: 1

หมายเหตุ: Sieve ขนาด 10⁷ ใช้หน่วยความจำมาก อาจปรับขนาดตาม constraints จริงของโจทย์