C++에서 주어진 숫자 이하의 가장 큰 특수 소수(Special Prime) 찾는 방법

숫자 n이 주어졌을 때, n보다 작거나 같은 가장 큰 특수 소수(special prime)를 찾아야 합니다. 특수 소수란 자릿수를 하나씩 차례대로 붙여가며 만들어지는 모든 중간 숫자가 소수인 수를 의미합니다.

예를 들어 379를 살펴보면, 한 자리 숫자 3은 소수이고, 두 자리 숫자 37도 소수이며, 세 자리 숫자 379 역시 소수입니다. 이처럼 왼쪽부터 잘라 만든 모든 접두사가 소수일 때 그 수를 특수 소수라고 부릅니다.

접근 방법: 에라토스테네스의 체

이 문제는 에라토스테네스의 체(Sieve of Eratosthenes)를 활용하면 효율적으로 해결할 수 있습니다. 전체 과정은 다음과 같습니다.

N까지의 범위로 체(sieve) 배열을 생성하여 각 숫자의 소수 여부를 미리 계산합니다.
N부터 1씩 줄여가며 해당 숫자가 소수인지 확인합니다.
소수라면 마지막 자릿수를 하나씩 제거하면서 남은 모든 숫자도 소수인지 검사합니다.
모든 조건을 통과하는 첫 번째 숫자가 곧 정답이 됩니다.

C++ 구현 코드

#include<iostream>
using namespace std;

// num의 모든 접두사가 소수인지 검사
bool isSpecialPrime(bool sieve[], int num) {
    while (num) {
        if (!sieve[num]) {
            return false;
        }
        num /= 10; // 마지막 자릿수 제거
    }
    return true;
}

void findSpecialPrime(int N) {
    bool sieve[N + 10];
    for(int i = 0; i<N+10; i++){
        sieve[i] = true;
    }
    sieve[0] = sieve[1] = false;

    // 에라토스테네스의 체 생성
    for (long long i = 2; i <= N; i++) {
        if (sieve[i]) {
            for (long long j = i * i; j <= N; j += i) {
                sieve[j] = false;
            }
        }
    }

    // N부터 내려가며 가장 큰 특수 소수 탐색
    while (true) {
        if (isSpecialPrime(sieve, N)) {
            cout << N << ''\n'';
            break;
        }
        else
            N--;
    }
}

int main() {
    cout << "Special prime in range (2 -> 400): ";
    findSpecialPrime(400);
    cout << "Special prime in range (2 -> 100): ";
    findSpecialPrime(100);
}

실행 결과

Special prime in range (2 -> 400): 379
Special prime in range (2 -> 100): 79

코드 설명

isSpecialPrime() 함수는 num /= 10 연산으로 숫자의 마지막 자릿수를 하나씩 제거해 가며, 남은 숫자가 체 배열에서 소수로 표시되어 있는지 확인합니다. 중간에 소수가 아닌 값이 하나라도 나오면 즉시 false를 반환합니다.

findSpecialPrime() 함수는 먼저 에라토스테네스의 체를 구성한 뒤, N부터 조건을 만족하는 수를 발견할 때까지 값을 감소시키며 탐색합니다. 그 결과 400 이하에서는 379(3 → 37 → 379 모두 소수), 100 이하에서는 79(7 → 79 모두 소수)가 가장 큰 특수 소수로 출력됩니다.