C++로 배열에서 연속된 소수의 최대 개수 구하기

문제 개요

크기가 N인 정수 배열이 무작위 순서로 주어집니다. 이 배열 안에서 연속된 소수로 이루어진 가장 긴 구간의 길이를 찾는 것이 이번 문제의 목표입니다.

소수(Prime Number)란 약수가 정확히 두 개, 즉 1과 자기 자신뿐인 수를 말합니다. 2, 3, 5, 7, 11, 13 등은 소수에 해당하고, 4, 6, 8, 9, 10처럼 약수가 세 개 이상인 수는 모두 소수가 아닙니다. 참고로 1은 약수가 하나뿐이므로 소수에 포함되지 않습니다.

입력 · 출력 예시

입력 − Arr[] = { 1, 3, 5, 2, 6, 7, 13, 4, 9, 10 }

출력 − 3

설명 − 배열에 포함된 소수는 3, 5, 2, 7, 13입니다. 이 가운데 서로 맞닿아 있는 구간은 {3, 5, 2}와 {7, 13} 두 곳이며, 가장 긴 구간은 원소 3개를 가지므로 정답은 3입니다.

입력 − Arr[] = { 5, 7, 17, 27, 31, 21, 41 }

출력 − 3

설명 − 배열에 포함된 소수는 5, 7, 17, 31, 41입니다. 이 중 연속된 구간은 {5, 7, 17} 하나뿐이고 길이가 3이므로 정답은 3입니다.

풀이 접근 방식

정수 배열 Arr[]에는 소수와 소수가 아닌 수가 섞여 저장되어 있습니다.
isprime(int num) 함수는 num이 소수인지 검사합니다. 2부터 num/2까지의 어떤 수로도 나누어 떨어지지 않으면 소수로 판정합니다.
소수이면 isprime()이 1을 반환하고, 그렇지 않으면 0을 반환합니다.
primeSubarray(int arr[], int n) 함수는 배열과 배열의 크기를 매개변수로 받아, 연속된 소수 구간 중 가장 긴 길이를 반환합니다.
배열을 처음부터 끝까지 순회하면서 arr[i]가 소수가 아니면(isprime(arr[i]) == 0) 연속 카운트를 0으로 초기화합니다.
arr[i]가 소수라면 카운트를 1 증가시킵니다. 도중에 소수가 아닌 수를 만나면 카운트는 다시 0부터 시작됩니다.
매 단계에서 현재 카운트가 지금까지의 최댓값보다 크면 그 값을 maxC에 저장합니다.
순회가 끝나면 maxC를 결과로 반환합니다.

C++ 구현 예제

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

// 소수 판별 함수: 소수이면 1, 아니면 0을 반환한다
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; // 위 조건을 모두 통과하면 num은 소수이다
}

// 연속된 소수 구간의 최장 길이를 계산하는 함수
int primeSubarray(int arr[], int n){
    int count = 0;
    int maxSeq = 0;
    for (int i = 0; i < n; i++) {
        // 소수가 아니면 연속 카운트를 초기화
        if (isprime(arr[i]) == 0)
            count = 0;
        // 소수라면 카운트 증가 후 최댓값 갱신
        else {
            count++;
            maxSeq = count > maxSeq ? count : maxSeq;
        }
    }
    return maxSeq;
}

int main(){
    int arr[] = { 8, 4, 2, 1, 3, 5, 7, 9 };
    int n = 8;
    printf("배열에서 연속된 소수의 최대 개수 : %d", primeSubarray(arr, n));
    return 0;
}

실행 결과

위 코드를 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다 −

배열에서 연속된 소수의 최대 개수 : 3

복잡도 및 성능 개선 팁

이 풀이는 배열을 한 번만 순회하므로 순회 자체의 비용은 O(N)입니다. 다만 각 원소에 대해 소수 여부를 검사할 때 2부터 num/2까지 나누어 보기 때문에 검사 하나당 최대 O(num)의 시간이 걸리며, 전체 시간 복잡도는 O(N × M)(M은 배열의 최댓값)이 됩니다.

검사 범위를 num/2 대신 √num까지만 살펴도 충분합니다. num의 약수 쌍 중 하나는 반드시 √num 이하에 존재하기 때문입니다. 이렇게 수정하면 소수 판별 비용이 O(√num)으로 줄어들어 전체 성능이 크게 향상됩니다.

마무리

핵심은 배열을 한 번만 훑으면서 '현재 연속된 소수 개수'와 '역대 최장 길이' 두 변수만 유지하는 것입니다. 소수가 아닌 수를 만나는 순간 카운트를 0으로 되돌리고, 소수를 만날 때마다 최댓값을 갱신하면 별도의 추가 배열 없이도 정답을 간단히 구할 수 있습니다.