C++로 숫자의 홀수 자릿수 합이 소수인지 판별하는 방법

문제 개요

이 문제에서는 하나의 숫자 N이 주어지며, 우리의 과제는 이 숫자의 홀수 자리(odd place)에 있는 자릿수들의 합이 소수(prime number)인지 아닌지를 확인하는 것입니다.

소수 판별(Primality Test)이란 주어진 수가 소수인지 아닌지를 검사하기 위해 사용되는 알고리즘을 말합니다.

자릿수의 위치는 가장 오른쪽 자리부터 1번째로 세기 시작합니다. 예를 들어 3425에서 5는 1번째(홀수), 2는 2번째(짝수), 4는 3번째(홀수), 3은 4번째(짝수) 자리에 해당합니다.

예제로 문제 이해하기

입력: 3425
출력: No
설명: 홀수 자리 자릿수의 합 = 5 + 4 = 9 → 9는 소수가 아니므로 "No"

해결 접근 방법

이 문제는 비교적 간단한 방법으로 해결할 수 있습니다.

1. 숫자를 오른쪽 끝자리부터 한 자리씩 읽어 나가면서, 홀수 번째 위치에 있는 자릿수들만 모두 더합니다.
2. 구해진 합을 소수 판별 알고리즘으로 검사하여 소수인지 여부를 출력합니다.

아래 프로그램은 위 해결 방법을 구현한 것입니다.

C++ 구현 예제

#include <iostream>
using namespace std;
int oddSum(int n) {
   int sum = 0, pos = 1;
   while(n) {
      if (pos %2 == 1)
         sum += n%10;
      n=n/10;
      pos++;
   }
   return sum;
}
bool isPrimeNumber(int n){
   if (n <= 1)
      return false;
   if (n <= 3)
      return true;
   if (n % 2 == 0 || n % 3 == 0)
      return false;
   for (int i = 5; i * i <= n; i = i + 6)
      if (n % i == 0 || n % (i + 2) == 0)
         return false;
   return true;
}
int main() {
   int n = 1734;
   if (isPrimeNumber(oddSum(n)))
      cout<<"Sum of odd digit of the number "<<n<<" is prime Number.";
   else
      cout<<"Sum of odd digit of the number "<<n<<" is not prime Number.";
   return 0;
}

실행 결과

Sum of odd digit of the number 1734 is prime Number.

코드 동작 원리

oddSum 함수는 숫자를 10으로 나누며 마지막 자릿수(n%10)를 하나씩 추출하고, 현재 위치(pos)가 홀수일 때만 해당 자릿수를 합계에 더합니다. 모든 자릿수를 처리한 뒤 홀수 자리 자릿수의 합을 반환합니다.

isPrimeNumber 함수는 효율적인 소수 판별 기법을 사용합니다. 2와 3으로 나누어 떨어지는 경우를 먼저 제외한 후, 6k±1 형태의 수(5, 7, 11, 13...)만 검사하여 √n까지 확인함으로써 시간 복잡도를 O(√n)으로 줄입니다.

예제에서 n = 1734인 경우, 홀수 자리 자릿수는 4와 7이므로 합은 11이 되고, 11은 소수이므로 "prime Number"라는 결과가 출력됩니다.