C++で素数の数字（2・3・5・7）のみで構成されるn番目の数を効率的に求める方法

この記事では、整数Nが与えられたときに、「素数の数字（2、3、5、7）のみで構成される数列」のN番目の数を求めるアルゴリズムを解説します。

素数の数字だけで構成される数列は、次のように並びます。

2, 3, 5, 7, 22, 23, 25, 27, 32, 33, ...

問題を理解するための例

入力：N = 6
出力：23

この場合、数列の6番目の要素は「23」となるため、出力は23です。

解法のアプローチ

この問題を解くシンプルな方法は、数列の規則性を観察することです。まず、与えられたインデックスNに対応する項を見つけることを考えます。

使用できる数字が4種類（2、3、5、7）しかないため、この数列は「4進法の数体系」として扱うことができます。つまり、長さxの数は全部で4^x個存在します。

具体的な手順は以下の通りです。

1. まず、N番目の数が何桁の数に属するかを特定します。各桁数ごとの個数（4、16、64...）を累積していき、Nがどの範囲に入るかを調べます。
2. 次に、その桁数の中でN番目に相当する位置を計算し、対応する数字（2、3、5、7）を1桁ずつ決定していきます。
3. 最後に、決定した桁を連結して答えを出力します。

C++での実装例

以下は、上記のアプローチを実装したC++プログラムです。

#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

まとめ

このように、素数の数字のみで構成される数列は4進法と同じ構造を持っているため、各桁の個数を累積的に調べることで、N番目の数を効率よく求めることができます。全ての数を生成して数え上げる方法（総当たり）に比べ、計算量を大幅に抑えられるのがこの手法の大きな利点です。