C++를 활용해 주어진 범위에서 가장 큰 쌍둥이 소수 찾기

이 문제에서는 두 개의 값 lValue(하한)와 hValue(상한)가 주어지며, 우리의 목표는 해당 범위 안에서 가장 큰 쌍둥이 소수(twin primes)를 찾는 것입니다.

여기서 쌍둥이 소수란 두 수가 모두 소수이면서 그 차이가 정확히 2인 숫자 쌍을 의미합니다.

문제 이해를 위한 예시

입력 : lValue = 65, rValue = 100
출력 : 71, 73

65부터 100 사이에서 차이가 2인 소수 쌍은 여러 개 있을 수 있지만, 그중 가장 큰 값인 (71, 73)이 정답이 됩니다.

해결 방법

방법 1: 단순 반복 탐색

가장 간단한 방법은 상한값에서 하한값까지 역방향으로 반복하면서 각각의 i와 i+2 쌍이 모두 소수인지 검사하고, 조건을 만족하는 첫 번째(즉, 가장 큰) 쌍을 출력하는 것입니다.

방법 2: 에라토스테네스의 체 활용

보다 효율적인 접근 방식은 먼저 주어진 범위 내의 모든 소수를 에라토스테네스의 체(Sieve of Eratosthenes)를 사용해 미리 구해 놓은 뒤, 큰 수부터 역순으로 탐색하며 i와 i+2가 모두 소수인 가장 큰 쌍을 찾는 것입니다. 소수 판별을 미리 완료하기 때문에 전체 실행 시간을 크게 줄일 수 있습니다.

C++ 구현 예제

아래 프로그램은 위에서 설명한 해결 방법의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
void findLargestTwins(int lValue, int uValue) {
    bool primes[uValue + 1];
    memset(primes, true, sizeof(primes));
    primes[0] = primes[1] = false;
    // 에라토스테네스의 체로 범위 내 모든 소수 계산
    for (int p = 2; p <= floor(sqrt(uValue)) + 1; p++) { 
        if (primes[p]) {
            for (int i = p * 2; i <= uValue; i += p)
            primes[i] = false;
        }
    }
    // 큰 수부터 역순으로 쌍둥이 소수 탐색
    int i;
    for (i = uValue; i >= lValue; i--) {
        if (primes[i] && (i - 2 >= lValue && primes[i - 2] == true)) {
            break;
        }
    }
    if(i >= lValue )
        cout<<"주어진 범위에서 가장 큰 쌍둥이 소수: ("<<(i-2)<<", "<<i<<")";
    else 
        cout<<"쌍둥이 소수가 존재하지 않습니다.";
}
int main(){
   int lValue = 54;
   int uValue = 102;
   findLargestTwins(lValue, uValue);
   return 0;
}

출력 결과

주어진 범위에서 가장 큰 쌍둥이 소수: (71, 73)

코드 설명

먼저 primes 배열을 초기화하여 범위 내 모든 수를 잠재적 소수로 표시한 후, 0과 1은 소수가 아니므로 false로 설정합니다. 이후 제곱근까지만 순회하며 배수들을 지워 나가는 방식으로 소수 목록을 완성합니다. 마지막으로 상한값부터 하한값까지 거꾸로 살펴보며 i와 i-2가 모두 소수인 최초의 지점을 찾아 결과를 출력합니다. 만약 범위 내에 쌍둥이 소수가 하나도 없다면 그에 맞는 메시지를 반환합니다.