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

C++ 배열에서 모든 합성수의 곱 구하기

정수 n개로 이루어진 배열 arr[n]이 주어졌을 때, 배열에 포함된 모든 합성수(composite number)의 곱을 구하는 것이 이번 글에서 다룰 문제입니다.

합성수란 무엇인가?

합성수는 1과 자기 자신 이외의 약수를 가지는 수, 즉 두 개 이상의 자연수를 곱하여 만들 수 있는 자연수를 뜻합니다. 예를 들어 6은 2와 3을 곱해 만들 수 있으므로 합성수입니다. 쉽게 말해 소수가 아닌 1보다 큰 자연수라고 할 수 있습니다.

입력 예시 1

arr[] = {1, 2, 4, 5, 6, 7}

출력

24

설명: 배열 속 합성수는 4와 6이며, 두 수의 곱은 4 × 6 = 24입니다.

입력 예시 2

arr[] = {10, 2, 4, 5, 6, 11}

출력

240

설명: 배열 속 합성수는 10, 4, 6이며, 세 수의 곱은 10 × 4 × 6 = 240입니다.

문제 해결 접근 방식

  • 배열의 모든 요소를 한 번씩 순회합니다.

  • 각 요소가 소수인지 아닌지를 판별합니다. 소수가 아니면서 1보다 큰 수가 바로 합성수입니다.

  • 판별된 합성수들을 모두 곱합니다.

  • 최종 곱을 반환합니다.

여러 개의 수에 대해 소수 여부를 빠르게 판별하기 위해 에라토스테네스의 체(Sieve of Eratosthenes)를 사용합니다. 배열의 최댓값까지 소수 테이블을 미리 만들어 두면 각 요소를 상수 시간에 판별할 수 있습니다.

알고리즘

Start
Step 1 → 배열 내 합성수의 곱을 구하는 함수 선언
    int product_arr(int arr[], int size)
        배열의 최댓값 max를 구한다
        크기가 max + 1인 vector<bool> prime을 true로 초기화
        prime[0] = true, prime[1] = true로 설정 (0과 1은 합성수가 아니므로 제외)
        For i = 2 부터 i * i <= max 까지 반복
            IF (prime[i] == true)
                For j = i * 2 부터 j <= max 까지 j += i 간격으로 반복
                    prime[j] = false 설정
                End
            End
        End
        product = 1로 초기화
        For i = 0 부터 i < size 까지 반복
            IF (!prime[arr[i]])  // 합성수라면
                product *= arr[i]
            End
        End
        return product
Stop

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
// 배열에서 합성수들의 곱을 구하는 함수
int product_arr(int arr[], int size){
    int max = *max_element(arr, arr + size);
    vector<bool> prime(max + 1, true);
    prime[0] = true; // 0과 1은 합성수가 아니므로 제외
    prime[1] = true;
    // 에라토스테네스의 체로 소수 판별
    for (int i = 2; i * i <= max; i++){
        if (prime[i] == true){
            for (int j = i * 2; j <= max; j += i)
                prime[j] = false;
        }
    }
    int product = 1;
    for (int i = 0; i < size; i++)
        if (!prime[arr[i]]){ // 소수가 아니면 합성수이므로 곱셈에 포함
            product *= arr[i];
        }
    return product;
}
int main(){
    int arr[] = { 2, 4, 6, 8, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"배열에 있는 합성수들의 곱: "<<product_arr(arr, size);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.

배열에 있는 합성수들의 곱: 1920

설명: 배열 {2, 4, 6, 8, 10} 중 합성수는 4, 6, 8, 10이며, 이들의 곱은 4 × 6 × 8 × 10 = 1920입니다.

복잡도 분석

에라토스테네스의 체를 구축하는 데 O(M log log M)(M은 배열의 최댓값), 배열 순회에 O(n)의 시간이 걸리므로 전체 시간 복잡도는 O(M log log M + n)입니다. 공간 복잡도는 소수 판별 테이블 저장을 위해 O(M)입니다.