หาจำนวน Prefix Sum ที่เป็นจำนวนเฉพาะในช่วงที่กำหนดด้วย C++

ในบทความนี้ เราต้องหาจำนวน Prefix Sum ที่เป็นจำนวนเฉพาะ ในอาร์เรย์ arr[] ของจำนวนเต็มบวก และ Range Query L, R โดยที่ L คือค่าดัชนีเริ่มต้น arr[L] สำหรับอาร์เรย์ prefixsum[] และ R คือจำนวน prefix sum ที่เราต้องการหา

เพื่อเติมอาร์เรย์ prefix sum เราเริ่มจากดัชนี L ถึงดัชนี R และบวกค่าปัจจุบันกับสมาชิกสุดท้ายในอาร์เรย์ที่กำหนด ตัวอย่าง:

Input : arr[ ] = { 3, 5, 6, 2, 4 } L = 1, R = 3 Output : 3 Explanation : prefixsum[0] = arr[L] = 5, prefixsum[1] = prefixsum[0] + arr[2] = 11, prefixsum[2] = prefixsum[1] + arr[3] = 13 ในอาร์เรย์ prefixsum[] ทั้งสามค่า 5, 11, 13 เป็นจำนวนเฉพาะในช่วงที่กำหนด
Input : arr[ ] = { 6, 10, 5, 8, 11 } L = 0, R = 3 Output : 1 Explanation : prefixsum[0] = 6, prefixsum[1] = 16, prefixsum[2] = 21, prefixsum[3] = 29 ในอาร์เรย์ prefixsum[] มีแค่ 29 ที่เป็นจำนวนเฉพาะ

วิธีการหาคำตอบ

จากโจทย์ เราสามารถสรุปได้ว่า เราต้องสร้างอาร์เรย์ prefixsum[] ใหม่ และเติมอาร์เรย์นั้นด้วยการบวกสมาชิกก่อนหน้าของ prefixsum[] กับสมาชิกปัจจุบันของอาร์เรย์ที่กำหนด สมาชิกแรกของ prefixsum[] จะเป็นค่าที่ดัชนี L ในอาร์เรย์ที่กำหนด

เราต้องรันลูปจาก L ถึง R โดยที่ L และ R เป็นช่วงของดัชนีที่จะประมวลผลในอาร์เรย์ที่กำหนด แล้วตรวจสอบสมาชิกของอาร์เรย์ prefixsum[] และเพิ่มตัวนับสำหรับทุกจำนวนเฉพาะที่พบ

ตัวอย่างโค้ด

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

vector<bool> checkprime(int *arr, int n, int MAX) {
    vector<bool> p(n);
    bool Prime_val[MAX + 1];
    for (int i = 2; i < MAX; i++)
        Prime_val[i] = true;
    Prime_val[1] = false;
    for (int p = 2; p * p <= MAX; p++) {
        if (Prime_val[p] == true) {
            for (int i = p * 2; i <= MAX; i += p)
                Prime_val[i] = false;
        }
    }
    for (int i = 0; i < n; i++) {
        if (Prime_val[arr[i]])
            p[i] = true;
        else
            p[i] = false;
    }
    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] == 1)
            count++;
    }
    cout << "Number of prefix sum prime in given range query: " << count;
    return 0;
}

ผลลัพธ์

Number of prefix sum prime in given range query: 2

คำอธิบายโค้ด

ในโค้ดนี้ เราสร้างอาร์เรย์ prefixsum[] และเติมด้วยผลรวมของสมาชิกก่อนหน้าของอาร์เรย์ prefixsum[] และสมาชิกปัจจุบันของอาร์เรย์ที่กำหนด หลังจากนั้น เราตรวจสอบตัวเลขทั้งหมดของ prefix array ว่าเป็นจำนวนเฉพาะหรือไม่ และที่นี่เราใช้演算法 Sieve of Eratosthenes เพื่อตรวจสอบจำนวนเฉพาะ สุดท้าย เพิ่มตัวนับสำหรับแต่ละจำนวนเฉพาะและแสดงผลลัพธ์

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวน Prefix Sum ที่เป็นจำนวนเฉพาะในช่วงที่กำหนด โดยใช้วิธี Naive และใช้ Sieve of Eratosthenes เพื่อหาจำนวนเฉพาะในอาร์เรย์ Prefix Sum เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python ได้เช่นกัน หวังว่าบทความนี้จะเป็นประโยชน์