C++로 소수 자릿수(2, 3, 5, 7)만으로 이루어진 n번째 숫자 찾기

문제 개요

이 문제에서는 숫자 N이 주어지며, 우리의 과제는 소수 자릿수(2, 3, 5, 7)만으로 이루어진 n번째 숫자를 찾는 것입니다.

소수 자릿수(2, 3, 5, 7)만으로 구성된 수열은 다음과 같습니다: 2, 3, 5, 7, 22, 23, 25, 27, 32, 33...

예시를 통해 문제를 이해해 보겠습니다:

입력: N = 6
출력: 23

수열에서 여섯 번째 숫자는 22 다음인 23이 됩니다.

해결 접근 방식

문제를 해결하는 간단한 방법은 주어진 인덱스에 해당하는 숫자, 즉 수열의 항을 직접 찾는 것입니다. 이를 위해서는 수열의 패턴을 관찰해야 합니다.

사용할 수 있는 소수 자릿수는 총 4개(2, 3, 5, 7)이므로, 이 수열을 하나의 4진법 숫자 체계로 간주할 수 있습니다. 이 체계에서 길이가 x인 숫자는 정확히 4^x개 존재합니다.

따라서 문제를 해결하려면 먼저 N번째 숫자가 몇 자리 숫자에 속하는지 길이(x)를 찾고, 그다음 해당 길이 범위 내에서 N번째 위치를 계산하여 원하는 숫자를 출력하면 됩니다.

구체적으로는 길이가 (x-1)인 숫자들의 누적 개수부터 세어 나가며, 남은 개수 N을 기준으로 각 자리의 값을 하나씩 결정합니다.

예제 코드

아래 프로그램은 위 해결 방식의 동작을 보여줍니다.

#include <iostream>
#include <math.h>
using namespace std;

void findNthNumber(int n){
   long x = 1;
   long lastNum = 0;
   while (true) {
      long currNum = lastNum + pow(4, x);
      if (lastNum < n && currNum >= n)
         break;
      x++;
      lastNum = currNum;
   }
   for (int i = 1; i <= x; i++) {
      for (long j = 1; j <= 4; j++) {
         if (lastNum + pow(4, x - i) < n)
            lastNum += pow(4, x - i);
         else {
            if (j == 1)
               cout<<"2";
            else if (j == 2)
               cout<<"3";
            else if (j == 3)
               cout<<"5";
            else if (j == 4)
               cout<<"7";
            break;
         }
      }
   }
}

int main(){
   int N = 32;
   cout<<N<<"번째 소수 자릿수 숫자는 ";
   findNthNumber(N);
   return 0;
}

출력 결과

32번째 소수 자릿수 숫자는 257

코드 동작 설명

위 코드의 동작을 단계별로 살펴보면 다음과 같습니다:

자릿수 길이 찾기: while 루프를 통해 N번째 숫자가 몇 자리 숫자인지 확인합니다. 길이 x인 숫자가 4^x개씩 존재하므로, 누적 개수가 N을 포함하게 될 때까지 x를 증가시킵니다.
각 자리 값 결정: 왼쪽 자리부터 차례대로 4개의 소수 자릿수(2, 3, 5, 7) 중 어느 것이 해당되는지 판단합니다. 각 자릿수가 차지하는 범위(4^x-i)와 비교하여 조건에 맞는 자릿수를 선택하고 출력합니다.

이 알고리즘의 시간 복잡도는 결과 숫자의 자릿수에 비례하므로 매우 효율적이며, 큰 N값에 대해서도 빠르게 답을 구할 수 있습니다.