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

C++로 주어진 곱을 만드는 서로 다른 두 소수 찾는 방법

개요

이 튜토리얼에서는 주어진 곱(곱셈의 결과값)을 만들 수 있는 두 개의 서로 다른 소수를 찾는 C++ 프로그램을 작성해 보겠습니다. 먼저 간단한 예시부터 살펴볼까요?

입력 − 21

출력 − 3 7

21 = 3 × 7이며, 3과 7은 모두 소수입니다. 이처럼 입력값을 두 소수의 곱으로 분해하는 것이 이번 문제의 핵심입니다.

문제 해결 접근 방법

핵심 아이디어는 간단합니다. 주어진 곱 이하의 모든 소수를 미리 구해두면, 곱이 입력값과 일치하는 두 소수의 쌍을 손쉽게 찾을 수 있습니다. 소수를 효율적으로 판별하기 위해 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용합니다. 전체 과정은 다음과 같습니다.

  1. 곱 값을 초기화하고, 범위 내 각 숫자가 소수인지 여부를 저장할 불리언 배열을 준비합니다.

  2. 에라토스테네스의 체를 이용해 주어진 곱 이하의 모든 소수를 찾아 배열에 기록합니다.

  3. 2부터 주어진 곱까지 반복하면서 다음 조건을 확인합니다.
    − 현재 숫자가 소수이고, n ÷ 현재 숫자의 결과 역시 소수인지 검사합니다.
    − 두 숫자가 서로 다르고, 그 곱이 정확히 n이라면 해당 쌍을 출력합니다.

예제 코드

위 접근 방식을 실제 코드로 구현한 내용입니다.

#include <bits/stdc++.h>
using namespace std;
bool primes(int n, bool primeStatus[]) {
    primeStatus[0] = primeStatus[1] = false;
    for (int i = 2; i <= n; i++) {
        primeStatus[i] = true;
    }
    for (int i = 2; i * i <= n; i++) {
        if (primeStatus[i] == true) {
            for (int j = i * 2; j <= n; j += i)
                primeStatus[j] = false;
        }
    }
}
int main() {
    int n = 21;
    bool primeStatus[n + 1], pairsFound = false;
    primes(n, primeStatus);
    for (int i = 2; i < n; i++) {
        int pair = n / i;
        if (primeStatus[i] && primeStatus[pair] && pair != i && pair * i == n) {
            cout << i << " " << pair << endl;
            pairsFound = true;
            break;
        }
    }
    if (!pairsFound){
        cout << "No pairs";
    }
    return 0;
}

실행 결과

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

3 7

복잡도 분석

− 시간 복잡도: O(n log log n) — 에라토스테네스의 체로 소수를 구하는 데 걸리는 시간입니다.
− 공간 복잡도: O(n) — 각 숫자의 소수 여부를 저장하는 불리언 배열이 필요합니다.

마무리

이번 튜토리얼에서는 에라토스테네스의 체를 활용해 주어진 곱을 만들 수 있는 두 개의 서로 다른 소수를 찾는 방법을 살펴보았습니다. 소수 판별 로직과 나눗셈 기반 짝 탐색만 이해하면 어떤 입력값에도 손쉽게 적용할 수 있습니다. 궁금한 점이 있다면 댓글로 남겨주세요!