จำนวนเฉพาะติดต่อกันสูงสุดในอาร์เรย์ใน C++

ภาพรวมปัญหา

หาลำดับจำนวนเฉพาะที่ติดต่อกันยาวที่สุดในอาร์เรย์

ตัวอย่าง

Input: Arr[] = {1, 3, 5, 2, 6, 7, 13, 4, 9, 10}
Output: 3
Explanation: จำนวนเฉพาะ: 3,5,2,7,13 ติดต่อกัน: {3,5,2} และ {7,13} ยาวสุด = 3

Input: Arr[] = {5, 7, 17, 27, 31, 21, 41}
Output: 3
Explanation: {5, 7, 17} ติดต่อกัน 3 ตัว

แนวทางแก้ปัญหา

• ฟังก์ชัน isprime() ตรวจสอบจำนวนเฉพาะ
• วนลูปอาร์เรย์: เจอจำนวนเฉพาะ -> เพิ่ม count, ไม่เจอ -> reset count
• อัปเดตค่าสูงสุดตลอด

ตัวอย่างโค้ด C++

#include <iostream>
#include <stdio.h>

int isprime(int num) {
    if (num <= 1) return 0;
    for (int i = 2; i <= num/2; i++)
        if (num % i == 0) return 0;
    return 1;
}

int primeSubarray(int arr[], int n) {
    int count = 0, maxSeq = 0;
    for (int i = 0; i < n; i++) {
        if (isprime(arr[i]) == 0) count = 0;
        else {
            count++;
            maxSeq = max(maxSeq, count);
        }
    }
    return maxSeq;
}

int main() {
    int arr[] = { 8, 4, 2, 1, 3, 5, 7, 9 };
    int n = 8;
    cout << "Maximum contiguous primes: " << primeSubarray(arr, n);
    return 0;
}

ผลลัพธ์

Maximum no. of contiguous Prime Numbers in an array: 3