문제 소개
정수 배열 arr[]가 주어졌을 때, 배열에 포함된 모든 소수의 곱을 구하는 것이 이번 문제의 목표입니다.
소수(素數)란 1과 자기 자신으로만 나누어 떨어지는 수, 즉 그 외의 어떤 수로도 나누어지지 않는 수를 의미합니다. 대표적인 소수로는 2, 3, 5, 7, 11 등이 있습니다. 참고로 1은 1과 자기 자신이 같은 수이므로 소수에 포함되지 않습니다.
주어진 배열에 대해 아래와 같은 결과를 얻어야 합니다.
입력 − arr[] = { 11, 20, 31, 4, 5, 6, 70 }
출력 − 1705
설명 − 배열 속 소수는 11, 31, 5이며, 이들의 곱은 11 × 31 × 5 = 1705입니다.
입력 − arr[] = { 1, 2, 3, 4, 5, 6, 7 }
출력 − 210
설명 − 배열 속 소수는 2, 3, 5, 7이며, 이들의 곱은 2 × 3 × 5 × 7 = 210입니다.
문제 해결 접근 방법
입력 배열 arr[]를 받습니다.
배열의 모든 요소를 순회하면서 각 요소가 소수인지 확인합니다.
배열에 존재하는 모든 소수를 서로 곱합니다.
최종 곱을 반환합니다.
알고리즘
시작
함수 int prodprimearr(int arr[], int n)
단계 1 → max_val을 max_element(arr, arr + n)의 값으로 선언 및 초기화
단계 2 → vector<bool> isprime(max_val + 1, true) 선언
단계 3 → isprime[0]과 isprime[1]을 false로 설정
단계 4 → p = 2부터 p * p <= max_val일 때까지 p를 1씩 증가하며 반복
만약 isprime[p] == true이면,
i = p * 2부터 i <= max_val일 때까지 i를 p씩 증가하며 반복
isprime[i]를 false로 설정
단계 5 → prod를 1로 설정
단계 6 → i = 0부터 i < n일 때까지 i를 1씩 증가하며 반복
만약 isprime[arr[i]]이면
prod = prod * arr[i]로 설정
단계 7 → prod 반환
함수 int main(int argc, char const *argv[])
단계 1 → arr[] = { 11, 20, 31, 4, 5, 6, 70 }으로 선언 및 초기화
단계 2 → n = sizeof(arr) / sizeof(arr[0])으로 선언 및 초기화
단계 3 → prodprimearr(arr, n)의 결과를 출력
종료예제 코드
#include <bits/stdc++.h>
using namespace std;
int prodprimearr(int arr[], int n){
// 배열의 최댓값 찾기
int max_val = *max_element(arr, arr + n);
// 에라토스테네스의 체를 이용해
// max_val 이하의 모든 소수 구하기
vector<bool> isprime(max_val + 1, true);
isprime[0] = false;
isprime[1] = false;
for (int p = 2; p * p <= max_val; p++) {
// isprime[p]가 변경되지 않았다면 p는 소수
if (isprime[p] == true) {
// p의 모든 배수를 소수가 아니라고 표시
for (int i = p * 2; i <= max_val; i += p)
isprime[i] = false;
}
}
// arr[]에 있는 모든 소수의 곱 계산
int prod = 1;
for (int i = 0; i < n; i++)
if (isprime[arr[i]])
prod *= arr[i];
return prod;
}
int main(int argc, char const *argv[]){
int arr[] = { 11, 20, 31, 4, 5, 6, 70 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << prodprimearr(arr, n);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
1705
동작 원리와 복잡도
이 풀이의 핵심은 에라토스테네스의 체(Sieve of Eratosthenes)입니다. 배열에서 가장 큰 값을 기준으로 소수 테이블을 한 번만 미리 만들어 두면, 이후에는 각 배열 요소가 소수인지 상수 시간(O(1))에 바로 확인할 수 있습니다.
시간 복잡도: 체를 구성하는 데 O(M log log M)(M은 배열의 최댓값), 배열 전체를 순회하는 데 O(N)이 걸리므로 전체 시간 복잡도는 O(M log log M + N)입니다.
공간 복잡도: 최댓값 크기의 불린 벡터가 필요하므로 O(M)입니다.
요소마다 일일이 제곱근까지만 나눠 보며 소수를 판별하는 방식(O(N√M))보다, 여러 번 조회해야 하는 경우에는 체를 사용하는 방식이 훨씬 효율적이라는 점을 기억해 두면 좋습니다.