Trong bài viết này, chúng ta cần tìm một số tổng tiền tố là số nguyên tố trong một mảng cho trước arr [] các số nguyên dương và truy vấn phạm vi L , R , ở đâu L là giá trị chỉ số ban đầu arr [L] cho mảng tiền tố [] và R là số tổng tiền tố chúng ta cần tìm.
Để điền vào mảng tổng tiền tố, chúng ta bắt đầu với chỉ số L đến chỉ số R và thêm giá trị hiện tại với phần tử cuối cùng trong mảng đã cho. Vì vậy, đây là Ví dụ cho vấn đề -
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. Phương pháp tiếp cận để tìm giải pháp
Nhìn vào vấn đề, chúng ta có thể nói rằng chúng ta cần tạo một tiền tố mảng mới [] và lấp đầy mảng đó bằng cách thêm phần tử trước đó của mảng tổng tiền tố và phần tử hiện tại của mảng đã cho. Phần tử đầu tiên của mảng tổng tiền tố sẽ là giá trị tại chỉ số L trong mảng đã cho.
Chúng ta cần chạy một vòng lặp từ L đến R trong đó L và R là một dải chỉ số để xử lý trong mảng đã cho, sau đó kiểm tra phần tử của mảng prefixsum [] và tăng số lượng cho mọi số nguyên tố tìm được.
Ví dụ
#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;
} Đầu ra
Number of prefix sum prime in given range query: 2
Giải thích về Quy tắc trên
Trong đoạn mã này, chúng ta đang tạo một tiền tố mảng [] và điền nó bằng tổng của phần tử trước đó của mảng tiền tố [] và phần tử hiện tại của mảng đã cho. Sau đó, chúng tôi đang kiểm tra tất cả các số mảng tiền tố cho các số nguyên tố và ở đây chúng tôi đang sử dụng thuật toán Sieve of Eratosthenes để kiểm tra các số nguyên tố. Cuối cùng, tăng số lượng cho mỗi số nguyên tố và hiển thị kết quả.
Kết luận
Trong bài viết này, chúng tôi đã giải quyết việc tìm kiếm một số nguyên tố tổng tiền tố trong một truy vấn phạm vi nhất định bằng cách áp dụng một cách tiếp cận đơn giản và sử dụng Sieve of Eratosthenes để tìm các số nguyên tố trong mảng tổng tiền tố. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết này hữu ích.