양의 정수로 이루어진 배열이 주어졌을 때, 배열 요소 중 최소 한 개가 소수에 해당하는 서로 다른 쌍(pair)의 개수를 구하는 것이 목표입니다. 예를 들어 배열이 [1, 2, 3, 4]라면 만들 수 있는 쌍은 (1,2), (1,3), (2,3), (2,4), (3,4) 입니다.
예제로 살펴보기
입력 − arr[] = { 1, 2, 4, 8, 10 }
출력 − 최소 한 개의 요소가 소수인 쌍의 개수: 4
설명 − 배열에서 유일한 소수는 2이며, 2와 나머지 모든 요소를 짝지으면 (1,2), (2,4), (2,8), (2,10)의 네 가지 쌍이 만들어집니다.
입력 − arr[] = { 0, 1, 4, 6, 15 }
출력 − 최소 한 개의 요소가 소수인 쌍의 개수: 0
설명 − 배열에 소수가 하나도 없기 때문에 조건을 만족하는 쌍은 존재하지 않습니다.
해결 접근 방법
핵심 아이디어는 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 소수 여부를 미리 계산해 두는 것입니다. 소수 판별 결과를 저장할 보조 배열 arr_2[]를 만들고, arr_2[i]가 0이면 i는 소수, 1이면 소수가 아니도록 표시합니다. 이후 각 쌍 (A, B)에 대해 arr_2[A]와 arr_2[B] 중 하나라도 0이라면 해당 쌍을 카운트합니다.
양의 정수로 이루어진 배열 arr[]를 입력받습니다.
check_prime(int temp, int arr_2[]) 함수는 최댓값 temp와 보조 배열 arr_2[]를 받아, 인덱스가 소수면 0, 아니면 1로 채웁니다.
0과 1은 소수가 아니므로 arr_2[0]과 arr_2[1]을 1로 설정합니다.
for 반복문으로 i = 2부터 i * i <= temp까지 순회하면서, arr_2[i]가 0(소수)인 경우에만 배수를 지워나갑니다.
내부 반복문으로 j = 2 * i부터 j <= temp까지 j += i씩 증가시키며 합성수에 해당하는 arr_2[j]를 1로 표시합니다.
Prime_Pairs(int arr[], int size) 함수는 배열과 그 크기를 받아, 최소 한 개의 요소가 소수인 쌍의 개수를 반환합니다.
카운트 변수 count를 0으로 초기화합니다.
temp = *max_element(arr, arr + size)로 배열의 최댓값을 구합니다.
길이가 temp + 1이고 0으로 초기화된 배열 arr_2[]를 만든 뒤 check_prime(temp, arr_2)를 호출합니다.
이제 arr_2[i]는 i가 소수면 0, 소수가 아니면 1의 값을 갖습니다.
두 개의 for 반복문으로 i = 0부터 i < size까지, j = i + 1부터 j < size까지 순회하며 각 쌍 (arr[i], arr[j])에 대해 arr_2[arr[i]] == 0 또는 arr_2[arr[j]] == 0인지 확인하고, 참이면 count를 증가시킵니다.
모든 반복이 끝난 후 count를 결과로 반환합니다.
전체 시간 복잡도는 체 생성에 O(M log log M)(M은 배열의 최댓값), 쌍 탐색에 O(N²)(N은 배열의 크기)이 소요되므로 O(M log log M + N²)입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void check_prime(int temp, int arr_2[]){
arr_2[0] = 1;
arr_2[1] = 1;
for(int i = 2; i * i <= temp; i++){
if (arr_2[i]==0){
for (int j = 2 * i; j <= temp; j += i){
arr_2[j] = 1;
}
}
}
}
int Prime_Pairs(int arr[], int size){
int count = 0;
int temp = *max_element(arr, arr + size);
int arr_2[temp + 1];
memset(arr_2, 0, sizeof(arr_2));
check_prime(temp, arr_2);
for (int i = 0; i < size; i++){
for (int j = i + 1; j < size; j++){
if (arr_2[arr[i]] == 0 || arr_2[arr[j]] == 0){
count++;
}
}
}
return count;
}
int main(){
int arr[] = { 3, 5, 2, 7, 11, 14 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs in an array such that at least one element is prime are: "<<Prime_Pairs(arr, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of pairs in an array such that at least one element is prime are: 15
배열 { 3, 5, 2, 7, 11, 14 }에서 소수가 아닌 요소는 14뿐이므로, 전체 쌍 C(6,2) = 15개 중 14만으로 이루어진 쌍은 존재하지 않습니다. 따라서 모든 15개의 쌍이 조건을 만족하게 됩니다.