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...

문제를 이해하기 위해 예를 들어 보겠습니다.

Input: N = 6
Output: 23

솔루션 접근 방식

문제를 푸는 간단한 방법은 주어진 색인에서 숫자를 찾는 것입니다. 즉, 급수의 항을 찾는 것입니다. 이를 위해 급수를 관찰할 것입니다.

우리는 4개의 다른 소수를 가지고 있으므로 만들어진 시리즈는 4자리 숫자 체계로 취급될 수 있습니다. 이 숫자 체계에서 길이 x의 4배 숫자가 있습니다.

이제 문제를 해결하기 위해 숫자를 생성하게 만든 숫자 o의 길이를 찾는 시리즈가 있습니다. 그런 다음 N번째 숫자를 계산하고 필요한 숫자를 인쇄합니다.

길이를 사용하여 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<<"th number made of prime digits is ";
   findNthNumber(N);
   return 0;
}

출력

32th number made of prime digits is 257