用C ++中的素数求和子数组
给我们一个正整数数组。目的是找到数组中数字的子数组，以使每个子数组都将和作为素数。如果数组是{1,2,3,4}。然后，子数组将为{1,2}，{2,3}，{3,4}。此类子数组的数量为3。
让我们用例子来理解
输入−arr[]={1,3,5,3,2};
输出-素数总和的子数组计数为：3
解释-子数组将是：{3,2}sum=5素数，{3,5,3}sum=11素数，{3,5,3,2}sum是13素数。
输入−arr[]={2,4,6};
输出-具有素数和的子数组的计数为：0
说明-所有子数组都具有非素数和。{2,4}=6，{4,6}=10
以下程序中使用的方法如下
我们将使用筛子查找所有小于最大值107的质数，并将其存储在vector<bool>检查中。如果任何数字为素数，则check[i]为true，否则为false。然后使用两个for循环遍历该数组，继续在子数组的和中添加元素，并使用check[sum]检查它是否为素数。如果是，则用素数和增加子数组的计数。
取正整数的数组arr[]。
函数sub_prime（intarr[]，intsize）接收数组，并返回以sum为质数的子数组的计数。
将初始计数设为0。
将temp=pow(10,7)初始化为最大值。
用true初始化向量检查。
check[0]和check[1]为假，因为它们不是素数。
从i=2到i*i<temp。所有数字均为假，因为它们不是非素数。
现在，如果我是素数，向量check[i]为true，否则为false。
再次遍历数组使用两个for循环。
将可变总数作为子数组中元素的总和。Arr[i]到arr[j]。其中i=0到i<size-1，j=i+1到j<size。
如果有任何check[total]为true。（总和为素数）。增量计数。
结果在所有循环结束时返回计数。
示例
#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