Chúng ta được cung cấp một mảng các số nguyên dương. Mục đích là tìm các mảng con của các số trong một mảng sao cho mỗi mảng con có tổng là số nguyên tố. Nếu mảng là {1,2,3,4}. Khi đó, các mảng con sẽ là {1,2}, {2,3}, {3,4}. Tổng số mảng con như vậy là 3.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - arr [] ={1,3,5,3,2};
Đầu ra - Số mảng con có tổng Nguyên tố là:3
Giải thích - Các phân thức con sẽ là:{3,2} sum =5 nguyên tố, {3,5,3} sum =11 nguyên tố và tổng {3,5,3,2} là 13 nguyên tố.
Đầu vào - arr [] ={2,4,6};
Đầu ra - Đếm các mảng con có tổng nguyên tố là:0
Giải thích - Tất cả các mảng con đều có tổng không nguyên tố. {2,4} =6, {4,6} =10
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng tôi sẽ tìm tất cả các số nguyên tố nhỏ hơn giá trị lớn nhất 107 bằng cách sử dụng một cái sàng và lưu nó trong kiểm tra vectơ
-
Lấy một mảng arr [] của các số nguyên dương.
-
Hàm sub_prime (int arr [], int size) nhận mảng và trả về số lượng các mảng con có tổng là số nguyên tố.
-
Lấy số lượng ban đầu là 0.
-
Khởi tạo temp =pow (10,7) làm giá trị lớn nhất.
-
Khởi tạo kiểm tra vectơ với true.
-
kiểm tra [0] và kiểm tra [1] có sai vì chúng không phải là số nguyên tố.
-
Từ i =2 đến i * i
-
Bây giờ kiểm tra vectơ [i] là đúng nếu tôi là số nguyên tố khác là sai.
-
Đảo ngược mảng một lần nữa bằng cách sử dụng hai vòng lặp for.
-
Lấy tổng biến làm tổng của các phần tử trong mảng con. Arr [i] thành arr [j]. Trong đó i =0 đến i
-
Nếu bất kỳ kiểm tra nào [tổng số] là đúng. (tổng tổng là số nguyên tố). Số lượng tăng dần.
-
Kết quả là số lượng trả về ở cuối tất cả các vòng lặp.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of subarrays with Prime sum are: 1