数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中统计素数和子数组
给定一个正整数数组。目标是找到数组中数字的子数组，使得每个子数组的和为素数。如果数组是 { 1,2,3,4 }，则子数组将是 {1,2}，{2,3}，{3,4}。此类子数组的数量为 3。
让我们通过例子来理解
输入 − arr[] = {1,3,5,3,2 };
输出 − 素数和子数组的数量为：3
解释 − 子数组将是：{ 3,2} 和=5 素数，{3,5,3} 和=11 素数，{3,5,3,2} 和为 13 素数。
输入 − arr[] = {2,4,6 };
输出 − 素数和子数组的数量为：0
解释 − 所有子数组的和都不是素数。{2,4}=6，{4,6}=10
下面程序中使用的方法如下
我们将使用筛法找到小于最大值 107 的所有素数，并将其存储在 vector<bool> check 中。如果任何数字是素数，则 check[i] 为真，否则为假。然后使用两个 for 循环遍历数组，将元素添加到子数组的和中，并使用 check[sum] 检查它是否是素数。如果是，则增加素数和子数组的数量。
取一个正整数数组 arr[]。
函数 sub_prime(int arr[], int size) 获取数组并返回和为素数的子数组的数量。
将初始计数设置为 0。
初始化 temp=pow(10,7) 作为最大值。
用 true 初始化向量 check。
check[0] 和 check[1] 为假，因为它们不是素数。
从 i=2 到 i*i<temp。所有数字都将为假，因为这些将不是素数。
现在，如果 i 是素数，则向量 check[i] 为真，否则为假。
使用两个 for 循环再次遍历数组。
取变量 total 作为子数组中元素的和。Arr[i] 到 arr[j]。其中 i=0 到 i<size-1，j=i+1 到 j<size。
如果任何 check[total] 为真。（总和为素数）。递增计数。
在所有循环结束时返回计数作为结果。
示例
#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
182 次浏览
