Computer >> 컴퓨터 >  >> 프로그래밍 >> C 프로그래밍

C++ 배열에서 최솟값·최댓값 소수 찾기

문제 설명

n개의 양의 정수로 이루어진 배열이 주어졌을 때, 배열에 들어 있는 수 중에서 값이 가장 작은 소수와 가장 큰 소수를 찾아야 합니다.

예를 들어 다음과 같은 배열이 주어졌다고 가정해 보겠습니다.

arr[] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33}
→ 최솟값 소수는 2, 최댓값 소수는 13입니다.

알고리즘

1. 입력 배열에서 최댓값을 구합니다. 이 값을 maxNumber라고 합니다.
2. 1부터 maxNumber까지의 소수를 모두 구해 동적 배열(vector)에 저장합니다.
3. 입력 배열을 순회하면서 저장된 소수 정보를 이용해 최솟값 소수와 최댓값 소수를 찾습니다.

예제 코드

아래 코드는 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 1부터 maxNumber까지의 소수 여부를 미리 계산한 뒤, 배열을 한 번만 순회하면서 답을 구합니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

void printMinAndMaxPrimes(int *arr, int n) {
    int maxNumber = *max_element(arr, arr + n);
    vector<bool> primes(maxNumber + 1, true);
    primes[0] = primes[1] = false;

    // 에라토스테네스의 체로 소수 여부 계산
    for (int p = 2; p * p <= maxNumber; ++p) {
        if (primes[p]) {
            for (int i = p * 2; i <= maxNumber; i += p) {
                primes[i] = false;
            }
        }
    }

    int minPrime = INT_MAX;
    int maxPrime = INT_MIN;
    for (int i = 0; i < n; ++i) {
        if (primes[arr[i]]) {
            minPrime = min(minPrime, arr[i]);
            maxPrime = max(maxPrime, arr[i]);
        }
    }

    cout << "최솟값 소수 = " << minPrime << "\n";
    cout << "최댓값 소수 = " << maxPrime << "\n";
}

int main() {
    int arr[] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33};
    printMinAndMaxPrimes(arr, SIZE(arr));
    return 0;
}

출력 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

최솟값 소수 = 2
최댓값 소수 = 13

동작 원리와 성능

이 프로그램은 크게 세 단계로 동작합니다.

  1. 최댓값 탐색: max_element 함수로 배열 전체를 확인해 가장 큰 값을 찾습니다. 이 값이 소수 판별 범위의 상한이 됩니다.
  2. 소수 사전 계산: 에라토스테네스의 체를 이용해 0부터 maxNumber까지 각 수가 소수인지 bool형 벡터에 기록합니다.
  3. 결과 도출: 입력 배열의 각 요소를 인덱스로 삼아 소수 여부를 상수 시간(O(1))에 확인하고, 최솟값과 최댓값을 차례로 갱신합니다.

전체 시간 복잡도는 O(M + N)입니다. 여기서 M은 배열의 최댓값, N은 배열의 크기입니다. 같은 범위 내에서 소수 판별을 여러 번 수행해야 하는 경우, 매번 제곱근까지 나누어 검사하는 방식보다 훨씬 효율적이라는 장점이 있습니다.