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

C++로 배열에서 매 k번째 소수의 곱 구하기

배열 arr[n]에 n개의 소수가 저장되어 있고 정수 k가 주어졌을 때, 배열에서 매 k번째 소수의 곱을 구하는 것이 이 글의 목표입니다.

예를 들어 배열이 arr[] = {3, 5, 7, 11}이고 k = 2라고 가정해 보겠습니다. 이 경우 매 2번째 소수인 5와 11을 곱한 값, 즉 5 × 11 = 55를 결과로 출력해야 합니다.

소수란 무엇인가?

소수(prime number)란 1과 자기 자신 외에는 어떤 수로도 나누어 떨어지지 않는 자연수를 말합니다. 대표적인 소수로는 2, 3, 5, 7, 11, 13 등이 있습니다.

예제

입력: arr[] = {3, 5, 7, 11, 13}, k = 2
출력: 55
설명: 배열의 매 2번째 요소는 5와 11이며, 두 수의 곱은 55입니다.

입력: arr[] = {5, 7, 13, 23, 31}, k = 3
출력: 13
설명: 배열의 매 3번째 요소는 13이므로 출력값은 13입니다.

문제 해결 접근 방식

  • n개의 요소를 가진 입력 배열과 k를 받아, 매 k번째 요소의 곱을 구합니다.
  • 빠른 소수 판별을 위해 에라토스테네스의 체(Sieve of Eratosthenes)를 생성합니다.
  • 배열을 순회하면서 k번째 소수를 찾고, 찾을 때마다 product 변수에 곱해 누적합니다.
  • 최종 곱을 출력합니다.

알고리즘

시작
단계 1 -> MAX를 1000000으로 정의하고 초기화
단계 2 -> bool prime[MAX + 1] 선언
단계 3 -> createsieve() 함수
    memset(prime, true, sizeof(prime)) 호출
    prime[1] = false 설정
    prime[0] = false 설정
    p = 2부터 p * p <= MAX까지 반복하며 p++
        만약 prime[p] == true라면
            i = p * 2부터 i <= MAX까지 반복하며 i += p
            prime[i] = false 설정
단계 4 -> void productOfKthPrimes(int arr[], int n, int k)
    c = 0으로 초기화
    product = 1로 초기화
    i = 0부터 i < n까지 반복하며 i++
        만약 prime[arr[i]]라면
            c를 1 증가
            만약 c % k == 0이라면
                product = product * arr[i]
                c = 0으로 초기화
    product 출력
단계 5 -> main() 함수
    createsieve() 호출
    n = 5, k = 2 설정
    arr[n] = { 2, 3, 11, 13, 23 } 설정
    productOfKthPrimes(arr, n, k) 호출
종료

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
bool prime[MAX + 1];
void createsieve() {
    memset(prime, true, sizeof(prime));
    // 0과 1은 소수가 아닙니다
    prime[1] = false;
    prime[0] = false;
    for (int p = 2; p * p <= MAX; p++) {
        if (prime[p] == true) {
            // p의 모든 배수를 찾아 소수 표시를 제거합니다
            for (int i = p * 2; i <= MAX; i += p)
            prime[i] = false;
        }
    }
}
// 정답을 계산합니다
void productOfKthPrimes(int arr[], int n, int k) {
    // 발견한 소수의 개수를 셉니다
    int c = 0;
    // 소수들의 곱을 저장합니다
    long long int product = 1;
    // 배열을 순회합니다
    for (int i = 0; i < n; i++) {
        // 현재 수가 소수인 경우
        if (prime[arr[i]]) {
            c++;
            if (c % k == 0) {
                product *= arr[i];
                c = 0;
            }
        }
    }
    cout << product << endl;
}
// 메인 함수
int main() {
    // 소수 체를 생성합니다
    createsieve();
    int n = 5, k = 2;
    int arr[n] = { 2, 3, 11, 13, 23 };
    productOfKthPrimes(arr, n, k);
    return 0;
}

출력 결과

39

코드 설명

위 프로그램의 동작 흐름을 단계별로 살펴보겠습니다.

  1. 체(Sieve) 생성: createsieve() 함수는 에라토스테네스의 체 알고리즘을 사용해 0부터 1000000까지 범위의 수들이 소수인지 여부를 미리 계산해 둡니다. 덕분에 이후 소수 판별을 상수 시간(O(1))에 처리할 수 있습니다.
  2. 카운팅과 곱셈: productOfKthPrimes() 함수는 배열을 처음부터 끝까지 순회하며 각 요소가 소수인지 확인합니다. 소수를 발견할 때마다 카운터 c를 증가시키고, c가 k의 배수가 되는 시점에 해당 값을 product에 곱한 뒤 카운터를 초기화합니다.
  3. 오버플로 방지: 소수들을 계속 곱하다 보면 값이 매우 커질 수 있으므로, product 변수는 long long int 타입으로 선언했습니다.

예제 입력 {2, 3, 11, 13, 23}과 k = 2의 경우를 직접 확인해 보겠습니다. 첫 번째 소수 2 다음 두 번째 소수 3을 곱하고(3), 이후 세 번째 소수 11 다음 네 번째 소수 13을 곱해 최종 결과 3 × 13 = 39가 출력됩니다.