Tối đa hóa kích thước mảng bằng cách xóa đúng K mảng con để chỉ còn số nguyên tố C++

Cho mảng Arr[] kích thước N và số K. Phải xóa chính xác K mảng con liên tiếp sao cho các phần tử còn lại đều là số nguyên tố và số lượng phần tử còn lại lớn nhất.

Ví dụ

Arr = {4, 3, 3, 4, 3, 4, 3}, K = 2 → Output: 3
Xóa Arr[0]={4} và Arr[3..5]={4,3,4} → Còn {3,3,3} (3 số nguyên tố).

Arr = {7, 6, 2, 11, 8, 3, 12}, K = 2 → Output: 3
Xóa {6} và {8,3,12} → Còn {7,2,11}.

Thuật toán

1. Dùng Sieve Eratosthenes đánh dấu số nguyên tố ≤ 10⁵.
2. Lưu chỉ số các phần tử hợp số (không phải nguyên tố) vào vector compIdx.
3. Giữa 2 hợp số liên tiếp là một đoạn các số nguyên tố. Tính độ dài các đoạn này → vector primeSegs.
4. Sắp xếp primeSegs tăng dần.
5. Tính prefix sum của primeSegs.
6. Xét 3 trường hợp:
   • K == 0 và có hợp số → không thể (-1).
   • K ≥ số hợp số: xóa hết hợp số (mỗi hợp số 1 mảng con), dư K - compCnt mảng con xóa thêm số nguyên tố (mỗi mảng con xóa 1 số nguyên tố) → kết quả = N - K.
   • K < số hợp số: phải gom hợp số. Cần giữ K mảng con xóa → bỏ qua compCnt - K khoảng nguyên tố nhỏ nhất giữa các hợp số. Kết quả = N - compCnt - sum(primeSegs nhỏ nhất).

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 100000;
bool isComposite[MAXV];

void sieve() {
    for (int i = 2; i * i < MAXV; i++)
        if (!isComposite[i])
            for (int j = i * i; j < MAXV; j += i)
                isComposite[j] = true;
    isComposite[0] = isComposite[1] = true;
}

int maxPrimeArraySize(int arr[], int N, int K) {
    sieve();
    vector compIdx;
    for (int i = 0; i < N; i++)
        if (isComposite[arr[i]]) compIdx.push_back(i);
    
    if (K == 0 && !compIdx.empty()) return -1;
    if (compIdx.size() <= K) return N - K;
    
    vector primeSegs;
    for (int i = 1; i < compIdx.size(); i++)
        primeSegs.push_back(compIdx[i] - compIdx[i-1] - 1);
    
    sort(primeSegs.begin(), primeSegs.end());
    for (int i = 1; i < primeSegs.size(); i++)
        primeSegs[i] += primeSegs[i-1];
    
    int keepGaps = compIdx.size() - K; // Số khoảng nguyên tố phải giữ (bị xóa)
    int primesDeleted = primeSegs[keepGaps - 1];
    return N - (int)compIdx.size() - primesDeleted;
}

int main() {
    int arr[] = {7, 2, 3, 4, 3, 6, 3, 3};
    int N = 8, K = 2;
    cout << maxPrimeArraySize(arr, N, K); // Output: 6
    return 0;
}

Kết quả

6