在本文中，我们需要在给定的正整数数组 arr[ ] 中查找多个素数前缀和，并进行范围查询L、R ，其中 L 是 prefixsum[ ] 数组的初始索引值 arr[ L ]，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.
登录后复制
寻找解决方案的方法
从这个问题来看，我们可以说我们需要创建一个新数组 prefixsum[ ] 并通过添加 prefix sum 数组的前一个元素和给定数组的当前元素。前缀和数组的第一个元素将是给定数组中索引 L 处的值。
我们需要运行一个从 L 到 R 的循环，其中 L 和 R 是要在给定数组，然后检查 prefixsum[ ] 数组的元素并增加找到的每个素数的计数。
示例
#include
using namespace std;
vector checkprime (int *arr, int n, int MAX){
vector 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
