ในบทความนี้ เราต้องหาผลรวมนำหน้าจำนวนหนึ่งซึ่งเป็นจำนวนเฉพาะในอาร์เรย์ arr[ ] ที่กำหนดของจำนวนเต็มบวกและข้อความค้นหาช่วง L , ร โดยที่ L เป็นค่าดัชนีเริ่มต้น arr[ L ] สำหรับ prefixsum[ ] array และ R คือจำนวนคำนำหน้าที่เราต้องหา
ในการเติมอาร์เรย์ผลรวมนำหน้า เราเริ่มต้นด้วยดัชนี 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
In prefixsum[ ] array all three 5, 11 and 13 are prime numbers in prefix sum array in given range.
Input : arr[ ] = { 6, 10, 5, 8, 11 }
L = 0, R = 3
Output : 1
Explanation : prefixsum[ 0 ] = arr[ L ] = 6
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 1 ] = 16
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 2 ] = 21
prefixsum[ 3 ] = prefixsum[ 2 ] + arr[ 3 ] = 29
In prefixsum[ ] array only 29 is the prime number in prefix sum array given range. แนวทางในการหาแนวทางแก้ไข
เมื่อพิจารณาถึงปัญหาแล้ว เราสามารถพูดได้ว่าเราต้องสร้างส่วนนำหน้าอาร์เรย์ใหม่[ ] และเติมอาร์เรย์นั้นโดยเพิ่มองค์ประกอบก่อนหน้าของอาร์เรย์ผลรวมส่วนนำหน้าและองค์ประกอบปัจจุบันของอาร์เรย์ที่กำหนด องค์ประกอบแรกของอาร์เรย์ผลรวมคำนำหน้าจะเป็นค่าที่ดัชนี 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[p] is not changed, then
// it is a prime
if (Prime_val[p] == true){
// Update all multiples of p
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]);//size of given array
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
คำอธิบายของโค้ดด้านบน
ในโค้ดนี้ เรากำลังสร้าง array prefixsum[ ] และเติมด้วยผลรวมขององค์ประกอบก่อนหน้าของ prefixsum[ ] array และองค์ประกอบปัจจุบันของอาร์เรย์ที่กำหนด หลังจากนั้น เรากำลังตรวจสอบตัวเลขทั้งหมดของอาร์เรย์นำหน้าสำหรับจำนวนเฉพาะ และที่นี่เรากำลังใช้อัลกอริธึม Sieve of Eratosthenes เพื่อตรวจสอบจำนวนเฉพาะ สุดท้าย เพิ่มจำนวนเฉพาะแต่ละจำนวนและแสดงผล
บทสรุป
ในบทความนี้ เราได้แก้ไขการค้นหาจำนวน prefix sum prime ในการสืบค้นช่วงที่กำหนดโดยใช้วิธีการที่ไร้เดียงสาและใช้ Sieve of Eratosthenes เพื่อค้นหาจำนวนเฉพาะในอาร์เรย์ผลรวมนำหน้า เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์
