通过精确删除k个子数组以在C ++中使数组成为素数来最大化数组的大小
给定任务是从具有N个正数元素的给定数组Arr[]中精确删除K个子数组，以使该数组中的所有其余元素均为质数，并且剩余数组的大小最大。
输入值
Arr[]={4, 3, 3, 4, 3, 4, 3} , K=2输出结果
3
说明-K=2，这意味着仅2个子数组必须删除。
删除的子数组是Arr[0]和Arr[3…5]，这使数组Arr[]={3,3,3}保留所有素数元素和可能的最大大小。
输入值
Arr[]={7, 6, 2, 11, 8, 3, 12}, K=2输出结果
3
说明-删除的子数组为Arr[1]和Arr[4…6]，其余的素数数组为Arr[]={7,2,11}。
在以下程序中使用的方法如下
首先通过调用sieve()函数，使用Eratosthenes的筛子将所有素数存储到另一个数组prime[]中。
在函数MaxSize()中运行从i=0到i<N的循环，并将所有复合数字的索引号存储到int类型的向量vect中。
然后运行另一个循环，从i=1到i<vect.size，计算两个连续复合之间的素数，并将其存储到另一个int类型的向量diff中。
然后使用sort()函数对向量diff进行排序。
现在运行另一个循环，从i=1到i<diff.size()并计算该向量的前缀和，这将帮助我们知道需要删除多少个素数。
使用if语句检查不可能的情况，即当K=0且没有组合时。
如果K大于或等于合成数，则删除所有包含额外素数的合成，这些要删除的子数组的大小应为1，以获得最佳答案
如果K小于合成数，那么我们将必须删除那些包含合成的子数组，并且素数子数组不应属于此类别。
示例
#include <bits/stdc++.h>
using namespace std;
const int Num = 1e5;
bool prime[Num];
//Sieve of Eratosthenes
void sieve(){
for (int i = 2; i < Num; i++) {
if (!prime[i]){
for (int j = i + i; j < Num; j += i){
prime[j] = 1;
}
}
}
prime[1] = 1;
}
int MaxSize(int* arr, int N, int K){
vector<int> vect, diff;
//Inserting the indices of composite numbers
for (int i = 0; i < N; i++){
if (prime[arr[i]])
vect.push_back(i);
}
/*Computing the number of prime numbers between
two consecutive composite numbers*/
for (int i = 1; i < vect.size(); i++){
diff.push_back(vect[i] - vect[i - 1] - 1);
}
//Sorting the diff vector
sort(diff.begin(), diff.end());
//Computing the prefix sum of diff vector
for (int i = 1; i < diff.size(); i++){
diff[i] += diff[i - 1];
}
//Impossible case
if (K > N || (K == 0 && vect.size())){
return -1;
}
//Deleting sub-arrays of length 1
else if (vect.size() <= K){
return (N - K);
}
/*Finding the number of primes to be deleted
when deleting the sub-arrays*/
else if (vect.size() > K){
int tt = vect.size() - K;
int sum = 0;
sum += diff[tt - 1];
int res = N - (vect.size() + sum);
return res;
}
}
//Main function
int main(){
sieve();
int arr[] = { 7, 2, 3, 4, 3, 6, 3, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout<< MaxSize(arr, N, K);
return 0;
}输出结果
如果运行上面的代码，我们将获得以下输出-
6