C++でN番目のスマート数（Smart Number）を求める方法

「スマート数（Smart Number）」とは、3つ以上の異なる素因数を持つ整数のことです。この記事では、与えられた数 N に対して、N 番目のスマート数を求めるアルゴリズムとその C++ 実装を解説します。

スマート数の列は以下のように始まります。

30, 42, 60, 66, 70, 78...

例えば、最初のスマート数である 30 は、素因数として 2・3・5 の3つの異なる素数を持っているため、スマート数と判定されます。

アルゴリズム

• 求めたい番号 N を初期化します。
• カウント用の変数 count を 0 で初期化します。
• ある数が素数かどうかを判定する関数を作成します。
• ある数がスマート数かどうかを判定する関数を作成します。
• 最初のスマート数が 30 であるため、30 から順にループ処理を行います。
  • 素数判定関数を使って、現在の数がスマート数かどうかを確認します。
  • スマート数が見つかるたびに count を 1 ずつ増やします。
  • count が N と等しくなった時点で、その数を返します。

C++での実装

以下は、上記のアルゴリズムを C++ で実装したコードです。

#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
   if (n < 2) return false;
   for (int i = 2; i <= sqrt(n); i++) {
      if (n % i == 0) return false;
   }
   return true;
}
bool isSmartNumber(int n) {
   int count = 0;
   for (int i = 2; i < n; i++) {
      if (n % i == 0 && isPrime(i)) {
         count += 1;
      }
      if (count == 3) {
         return true;
      }
   }
return false;
}
int getNthSmartNumber(int n) {
   int i = 30, count = 0;
   while (true) {
      if (isSmartNumber(i)) {
         count += 1;
      }
      if (count == n) {
         return i;
      }
      i += 1;
   }
}
int main() {
   int N = 25;
   cout << getNthSmartNumber(N) << endl;
   return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。これは 25 番目のスマート数に相当します。

174

このように、素数判定と約数の探索を組み合わせることで、効率的に N 番目のスマート数を求めることができます。計算量をさらに抑えたい場合は、素因数分解を高速化する手法（試し割り法の範囲を √n までに限定するなど）を活用するとよいでしょう。