C++로 N 이하의 모든 반소수(Semiprime) 출력하기

이 문제에서는 하나의 정수 N이 주어지며, N보다 작거나 같은 모든 반소수(semiprime)를 찾아 출력해야 합니다.

본격적으로 문제를 해결하기 전에, 반소수가 정확히 무엇인지 먼저 살펴보겠습니다.

반소수(Semiprime)란?

반소수는 서로 다른 두 소수의 곱으로 표현되는 수를 의미합니다. 여기서 중요한 점은 두 소수가 반드시 서로 달라야 한다는 것입니다.

예를 들어 살펴보겠습니다.

• 21 = 3 × 7 → 서로 다른 두 소수의 곱이므로 반소수입니다.
• 25 = 5 × 5 → 같은 소수를 두 번 곱한 값이므로 반소수가 아닙니다.

문제 예시

N 이하의 반소수를 구하는 예시는 다음과 같습니다.

입력: N = 15
출력: 6 10 14 15

접근 방법

이 문제를 해결하는 기본적인 아이디어는 다음과 같습니다.

1. N 이하의 각 수를 차례대로 검사합니다.
2. 각 수가 정확히 두 개의 서로 다른 소인수를 가지는지 확인합니다.
3. 조건을 만족하는 수만 결과 목록에 추가합니다.

팁: 가장 작은 반소수는 6(= 2 × 3)이므로, 불필요한 연산을 줄이기 위해 검사 범위를 6부터 시작할 수도 있습니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> generateSemiPrimeNumbers(int n){
    int index[n + 1];
    for (int i = 1; i <= n; i++)
        index[i] = i;

    int countDivision[n + 1];
    for (int i = 0; i < n + 1; i++)
        countDivision[i] = 2;

    for (int i = 2; i <= n; i++) {
        if (index[i] == i && countDivision[i] == 2) {
            for (int j = 2 * i; j <= n; j += i) {
                if (countDivision[j] > 0) {
                    index[j] = index[j] / i;
                    countDivision[j]--;
                }
            }
        }
    }

    vector<int> semiPrime;
    for (int i = 2; i <= n; i++) {
        if (index[i] == 1 && countDivision[i] == 0)
            semiPrime.push_back(i);
    }
    return semiPrime;
}

int main(){
    int n = 15;
    cout<<"Semi-prime numbers less than or equal to "<<n<<" are :\n";
    vector<int> semiPrime = generateSemiPrimeNumbers(n);
    for (int i = 0; i < semiPrime.size(); i++)
        cout<<semiPrime[i]<<"\t";
    return 0;
}

실행 결과

15 이하의 반소수는 다음과 같습니다.

6    10    14    15

코드 동작 원리

이 알고리즘은 에라토스테네스의 체와 유사한 방식으로 동작합니다.

• index 배열은 각 수의 값을 저장하고, 소수로 나눌 때마다 그 값을 해당 소수로 나누어 갱신합니다.
• countDivision 배열은 각 수가 나눠질 수 있는 남은 횟수를 추적하며, 초기값은 2로 설정됩니다.
• 모든 과정이 끝난 후 index[i] == 1(완전히 나누어짐)이고 countDivision[i] == 0(정확히 두 번 나누어짐)인 수가 바로 반소수입니다.

이 방식을 사용하면 각 수를 일일이 소인수분해하는 것보다 효율적으로 N 이하의 모든 반소수를 구할 수 있습니다.