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;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

如果我们运行上面的代码，它将生成以下输出：

Count of subarrays with Prime sum are: 1

更新于：2020年12月1日

182 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告