資料結構
網路
關係資料庫管理系統 (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 次瀏覽
