C++로 숫자가 완전 소수(Full Prime)인지 확인하는 방법

이 글에서는 주어진 숫자가 완전 소수(Full Prime)인지 판별하는 방법을 알아보겠습니다. 완전 소수란 숫자 자체가 소수이면서, 그 숫자를 구성하는 모든 자릿수도 소수인 경우를 말합니다. 예를 들어 37은 37 자체가 소수이고 각 자릿수인 3과 7도 모두 소수이므로 완전 소수입니다. 반면 97은 숫자 자체는 소수지만 자릿수 중 9가 소수가 아니기 때문에 완전 소수가 아닙니다.

효율적인 접근 방법

가장 효율적인 방법은 다음 두 단계로 검사를 진행하는 것입니다.

먼저, 숫자를 구성하는 각 자릿수 중 소수가 아닌 것이 있는지 확인합니다. 자릿수는 0부터 9 사이의 값만 가질 수 있으며, 이 범위에서 소수는 2, 3, 5, 7뿐입니다. 따라서 나머지 숫자(0, 1, 4, 6, 8, 9)가 하나라도 포함되어 있다면 즉시 완전 소수가 아닌 것으로 판단할 수 있습니다.

모든 자릿수가 소수라면, 다음으로 그 숫자 전체가 소수인지 검사합니다. 두 조건을 모두 만족할 때만 해당 숫자를 완전 소수로 판정합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

// 일반적인 소수 판별 함수
bool isPrime(int n) {
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// 모든 자릿수가 소수인지 확인하는 함수
bool isDigitPrime(int n) {
    int temp = n, digit;
    while (temp) {
        digit = temp % 10;
        // 자릿수가 2, 3, 5, 7이 아니면 소수가 아님
        if (digit != 2 && digit != 3 && digit != 5 && digit != 7) {
            return false;
        }
        temp = temp / 10;
    }
    return true;
}

// 완전 소수 판별 함수
bool isFullPrime(int n) {
    return (isDigitPrime(n) && isPrime(n));
}

int main() {
    int num = 37;
    if (isFullPrime(num)) {
        cout << "The number is Full Prime";
    } else {
        cout << "The number is not Full Prime";
    }
}

실행 결과

The number is Full Prime

코드 설명

isDigitPrime 함수는 숫자를 한 자리씩 나누어(% 10) 각 자릿수를 추출한 뒤, 해당 값이 2, 3, 5, 7 중 하나인지 검사합니다. 소수가 아닌 자릿수를 발견하면 바로 false를 반환하여 불필요한 연산을 줄입니다.

isFullPrime 함수는 논리 AND 연산(&&)을 사용해 자릿수 검사와 소수 검사를 모두 통과해야 true를 반환하도록 구현되어 있습니다. 이처럼 자릿수 검사를 먼저 수행하면 대부분의 숫자를 빠르게 걸러낼 수 있어 전체적인 효율이 향상됩니다.