นับอาร์เรย์ย่อยด้วย Prime sum ใน C++

เราได้รับอาร์เรย์ของจำนวนเต็มบวก เป้าหมายคือการหาอาร์เรย์ย่อยของตัวเลขในอาร์เรย์ที่แต่ละ subarray มีผลรวมเป็นจำนวนเฉพาะ ถ้าอาร์เรย์เป็น { 1,2,3,4 } จากนั้นอาร์เรย์ย่อยจะเป็น {1,2}, {2,3}, {3,4} จำนวนอาร์เรย์ย่อยดังกล่าวคือ 3

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − arr[] ={1,3,5,3,2 };

ผลผลิต − จำนวนอาร์เรย์ย่อยที่มีจำนวนเฉพาะคือ:3

คำอธิบาย − Subarrays จะเป็น:{ 3,2} sum=5 ไพรม์, {3,5,3} sum=11 ไพรม์ และ {3,5,3,2} ผลรวมคือ 13 ไพรม์

ป้อนข้อมูล − arr[] ={2,4,6 };

ผลผลิต − จำนวนอาร์เรย์ย่อยที่มีผลรวมเฉพาะ:0

คำอธิบาย − อาร์เรย์ย่อยทั้งหมดมีผลรวมที่ไม่ใช่จำนวนเฉพาะ {2,4}=6, {4,6}=10

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

เราจะค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าค่าสูงสุด 107 โดยใช้ตะแกรงและเก็บไว้ในกาเครื่องหมาย vector หากจำนวนใดเป็นจำนวนเฉพาะ ให้ตรวจสอบว่า[i] เป็นจริง มิฉะนั้น เป็นเท็จ จากนั้นสำรวจอาร์เรย์โดยใช้สองลูป เพิ่มองค์ประกอบต่อไปในผลรวมของอาร์เรย์ย่อย และตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่โดยใช้ check[sum] ถ้าใช่ ให้เพิ่มจำนวนสำหรับอาร์เรย์ย่อยด้วยผลรวมเฉพาะ

• หาอาร์เรย์ arr[] ของจำนวนเต็มบวก

• ฟังก์ชัน sub_prime(int arr[], int size) รับอาร์เรย์และส่งกลับจำนวนอาร์เรย์ย่อยที่มีผลรวมเป็นจำนวนเฉพาะ

• นับเริ่มต้นเป็น 0

• เริ่มต้น temp=pow(10,7) เป็นค่าสูงสุด

• เริ่มต้นการตรวจสอบเวกเตอร์ด้วยค่าจริง

• check[0] และ check[1] เป็นเท็จ เนื่องจากไม่ใช่ไพรม์

• จาก i=2 ถึง i*i

• ตอนนี้การตรวจสอบเวกเตอร์[i] เป็นจริงถ้าฉันเป็นจำนวนเฉพาะอย่างอื่นเป็นเท็จ

• Traverse array อีกครั้งโดยใช้ two for loops

• นำผลรวมของตัวแปรเป็นผลรวมขององค์ประกอบในอาร์เรย์ย่อย Arr[i] ถึง arr[j] โดยที่ i=0 ถึง i<ขนาด-1และ j=i+1 ถึง j<ขนาด

• หากมีการตรวจสอบใด ๆ [ทั้งหมด] เป็นจริง ( ผลรวมทั้งหมดเป็นจำนวนเฉพาะ ). จำนวนที่เพิ่มขึ้น

• นับกลับเมื่อสิ้นสุดการวนซ้ำทั้งหมดตามผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int sub_prime(int arr[], int size){
   int count = 0;
   int temp = int(pow(10, 7));
   vector check(temp + 1, true);
   check[0] = false;
   check[1] = false;
   for (int i = 2; i * i <= temp; i++){
      if (check[i] == true){
         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;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of subarrays with Prime sum are: 1