Số lượng số nguyên tố liên tiếp tối đa trong mảng C++

Cho mảng Arr[] kích thước N chứa các số nguyên. Tìm độ dài dãy con liên tiếp (subarray) dài nhất chỉ chứa số nguyên tố.

Ví dụ

Arr = {1, 3, 5, 2, 6, 7, 13, 4, 9, 10} → Output: 3
Số nguyên tố: 3,5,2,7,13. Dãy liên tiếp: {3,5,2} (độ dài 3) và {7,13} (độ dài 2).

Arr = {5, 7, 17, 27, 31, 21, 41} → Output: 3
Dãy {5, 7, 17} (độ dài 3).

Thuật toán

• Hàm isPrime(x) kiểm tra nguyên tố trong O(√x).
• Duyệt mảng, giữ biến curLen (độ dài dãy nguyên tố hiện tại) và maxLen.
• Nếu arr[i] nguyên tố: curLen++, cập nhật maxLen.
• Ngược lại: curLen = 0.

Chương trình C++

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

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int maxPrimeSubarray(int arr[], int n) {
    int cur = 0, best = 0;
    for (int i = 0; i < n; i++) {
        if (isPrime(arr[i])) {
            cur++;
            best = max(best, cur);
        } else cur = 0;
    }
    return best;
}

int main() {
    int arr[] = {8, 4, 2, 1, 3, 5, 7, 9};
    int n = 8;
    cout << "So nguyen to lien tiep toi da: " << maxPrimeSubarray(arr, n);
    return 0;
}

Kết quả

So nguyen to lien tiep toi da: 3

Tối ưu hóa

Nếu mảng lớn và giá trị ≤ 10⁶, dùng Sieve Eratosthenes tiền xử lý O(MAX log log MAX) rồi kiểm tra O(1).