C++에서 다른 모든 요소와 서로소인 배열 요소 찾기

양의 정수로 이루어진 배열 A[]가 있고, 모든 i에 대해 2 ≤ A[i] ≤ 10⁶의 범위를 가진다고 가정해 봅시다. 이때 우리의 과제는 배열 안에 적어도 하나의 요소가 존재하여, 그 요소가 배열의 다른 모든 요소들과 서로소(coprime) 관계를 이루는지 확인하는 것입니다.

예를 들어 배열이 {2, 8, 4, 10, 6, 7}이라고 해보겠습니다. 여기서 7은 배열의 다른 모든 요소와 서로소입니다. 7은 소수이고, 나머지 요소들은 모두 2를 소인수로 가지기 때문에 7과는 공약수가 없습니다.

효율적인 접근 방법

이 문제를 효율적으로 해결하려면, 주어진 배열에 있는 정수들의 모든 소인수를 생성해야 합니다. 어떤 요소가 다른 요소들과 공통된 소인수를 하나도 갖지 않는다면, 그 요소는 항상 다른 모든 요소와 서로소 쌍을 이룹니다.

이를 구현하기 위해 가장 작은 소인수(Smallest Prime Factor, SPF)를 미리 계산해 두는 체(Sieve) 기법을 활용하면, 각 수를 빠르게 소인수분해할 수 있습니다.

알고리즘 단계

SPF 전처리: 에라토스테네스의 체를 변형한 방식으로 1부터 MAX까지 각 수의 가장 작은 소인수를 미리 계산합니다.
소인수분해 및 카운팅: 배열의 각 요소를 SPF를 이용해 소인수분해하고, 각 소인수가 등장한 횟수를 해시 테이블에 기록합니다.
공통 소인수 검사: 각 요소의 소인수를 다시 확인하면서, 해당 소인수가 다른 요소에서도 등장했는지(카운트가 1보다 큰지) 검사합니다. 공통 소인수가 하나도 없는 요소가 존재하면 조건을 만족합니다.

예제 코드 (C++)

#include <iostream>
#define MAX 1000001
using namespace std;
int smallPrimeFactor[MAX];
// 소인수 등장 횟수를 저장하는 해시
int hash1[MAX] = { 0 };

// 각 수의 가장 작은 소인수를 미리 계산
void getSmallestPrimeFactor() {
    smallPrimeFactor[1] = 1;
    for (int i = 2; i < MAX; i++)
        smallPrimeFactor[i] = i;
    for (int i = 4; i < MAX; i += 2)
        smallPrimeFactor[i] = 2;
    for (int i = 3; i * i < MAX; i++) {
        if (smallPrimeFactor[i] == i) {
            for (int j = i * i; j < MAX; j += i)
                if (smallPrimeFactor[j] == j)
                    smallPrimeFactor[j] = i;
        }
    }
}

// x를 소인수분해하고 소인수 등장 횟수를 해시에 기록
void factorizationResult(int x) {
    int temp;
    while (x != 1) {
        temp = smallPrimeFactor[x];
        if (x % temp == 0) {
            hash1[smallPrimeFactor[x]]++;
            x = x / smallPrimeFactor[x];
        }
        while (x % temp == 0)
            x = x / temp;
    }
}

// x가 다른 요소와 공통 소인수를 가지는지 확인
bool hasCommonFactors(int x) {
    int temp;
    while (x != 1) {
        temp = smallPrimeFactor[x];
        if (x % temp == 0 && hash1[temp] > 1)
            return false;
        while (x % temp == 0)
            x = x / temp;
    }
    return true;
}

// 조건을 만족하는 요소가 존재하는지 확인
bool hasValueToFormCoPrime(int arr[], int n) {
    getSmallestPrimeFactor();
    for (int i = 0; i < n; i++)
        factorizationResult(arr[i]);
    for (int i = 0; i < n; i++)
        if (hasCommonFactors(arr[i]))
            return true;
    return false;
}

int main() {
    int arr[] = { 2, 8, 4, 10, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (hasValueToFormCoPrime(arr, n))
        cout << "There is a value, that can form Co-prime pairs with all other elements";
    else
        cout << "There is no value, that can form Co-prime pairs with all other elements";
}

출력 결과

There is a value, that can form Co-prime pairs with all other elements

코드 설명

getSmallestPrimeFactor(): 체 방식을 이용해 1부터 MAX-1까지 모든 수의 가장 작은 소인수를 O(MAX log log MAX) 시간에 계산합니다.
factorizationResult(int x): SPF 배열을 참조하며 x를 반복적으로 나누어 소인수분해하고, 각 소인수의 등장 횟수를 hash1 배열에 누적합니다.
hasCommonFactors(int x): x의 소인수 중 하나라도 다른 요소에서도 발견되었다면(hash1 값이 1보다 크면) false를 반환합니다. 모든 소인수가 x에서만 등장했다면 true를 반환합니다.
hasValueToFormCoPrime(int arr[], int n): 전체 흐름을 조합하여, 조건을 만족하는 요소의 존재 여부를 반환합니다.

시간 복잡도

SPF 전처리에 O(MAX log log MAX), 배열의 N개 요소에 대한 소인수분해 및 검사에 O(N log MAX)가 소요됩니다. 따라서 전체 시간 복잡도는 약 O(MAX log log MAX + N log MAX)이며, 일반적인 소인수분해 방식보다 훨씬 효율적입니다.