使用 C++ 在给定范围查询中查找前缀总和素数的数量

在本文中，我们需要在给定的正整数数组 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[] 并通过添加前缀 sum 数组的前一个元素和给定数组的当前元素来填充该数组。前缀和数组的第一个元素将是给定数组中索引 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++){
        // 如果prime[p]没有改变，那么
        // 这是一个素数
        if (Prime_val[p] == true){
            // 更新 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]);//给定数组的大小
    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 <<"给定范围查询中前缀和素数的数量： " << count;
    return 0;
}

给定范围查询中前缀和素数的数量： 2

以上代码说明

在这段代码中，我们创建了一个数组 prefixsum[] 并用 prefixsum[] 数组的前一个元素和给定数组的当前元素的总和填充它。之后，我们正在检查前缀数组的所有数字是否有素数，这里我们使用埃拉托色尼筛算法来检查素数。最后，增加每个素数的计数并显示结果。

结论

在本文中，我们通过应用一种朴素的方法并使用埃拉托色尼筛法在前缀和数组中查找素数来解决在给定范围查询中查找多个前缀和素数的问题。我们可以用其他语言编写相同的程序，例如 C、java、python 和其他语言。希望这篇文章对您有所帮助。