C++에서 주어진 곱을 만족하는 두 개의 서로 다른 소수 찾기

개요

이 튜토리얼에서는 C++을 활용하여 곱이 주어진 값과 같아지는 두 개의 서로 다른 소수를 찾는 프로그램을 다룹니다.

정수 N이 하나 주어지면, 곱이 N과 정확히 일치하는 소수 쌍을 찾는 것이 목표입니다. 예를 들어 N = 15라면 3 × 5 = 15이므로 정답은 3과 5입니다. 반면 N = 24처럼 어떤 소수 조합으로도 표현할 수 없는 경우에는 쌍이 존재하지 않는다고 출력해야 합니다.

알고리즘 접근 방식

에라토스테네스의 체를 이용해 N 이하의 모든 소수를 미리 구합니다.
2부터 N-1까지 반복하면서 각 수 i에 대해 몫 x = N / i를 계산합니다.
i와 x가 모두 소수이고 서로 다르며, i × x == N을 만족하면 해당 쌍을 출력하고 종료합니다.
끝까지 조건을 만족하는 쌍을 찾지 못하면 쌍이 존재하지 않음을 알립니다.

x를 N / i의 몫으로 바로 구하기 때문에 별도의 검증 없이도 두 수의 곱 관계가 자연스럽게 확인된다는 점이 이 방법의 핵심입니다.

C++ 구현 코드

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

// 에라토스테네스의 체로 N 이하의 소수를 미리 구함
void findingPrimeNumbers(int n, bool calcPrime[]) {
    calcPrime[0] = calcPrime[1] = false;
    for (int i = 2; i <= n; i++)
        calcPrime[i] = true;
    for (int p = 2; p * p <= n; p++) {
        if (calcPrime[p] == true) {
            for (int i = p * 2; i <= n; i += p)
                calcPrime[i] = false;
        }
    }
}

// 유효한 소수 쌍을 찾아 출력
void calcPairPrime(int n) {
    int flag = 0;
    bool calcPrime[n + 1];
    findingPrimeNumbers(n, calcPrime);
    for (int i = 2; i < n; i++) {
        int x = n / i;
        if (calcPrime[i] && calcPrime[x] and x != i and x * i == n) {
            cout << i << " " << x;
            flag = 1;
            return;
        }
    }
    if (!flag)
        cout << "No prime pair exist";
}

int main() {
    int n = 24;
    calcPairPrime(n);
    return 0;
}

실행 결과

No prime pair exist

N = 24는 2³ × 3으로 인수분해됩니다. 가능한 곱의 조합(2 × 12, 3 × 8, 4 × 6 등) 중 어느 경우에도 두 숫자가 모두 소수가 아니므로 유효한 소수 쌍이 존재하지 않습니다.

쌍이 존재하는 경우의 예시

만약 N = 35를 입력하면 i = 5일 때 x = 7이 되고, 5와 7은 모두 소수이며 5 × 7 = 35를 만족하므로 프로그램은 아래와 같이 출력합니다.

5 7

복잡도 분석

시간 복잡도: 에라토스테네스의 체 구성에 O(N log log N), 소수 쌍 탐색 루프에 O(N)이 소요되므로 전체 시간 복잡도는 O(N log log N)입니다.
공간 복잡도: 소수 판별 여부를 저장하는 불리언 배열 때문에 O(N)의 공간이 필요합니다.