C++のN番目のスマート番号

スマート数は、少なくとも3つの異なる素因数を含む数です。番号Nが与えられます。n番目のスマート番号を見つけます。

スマートナンバーシリーズは

30、42、60、66、70、78 ...

アルゴリズム

• 番号Nを初期化します。
• カウントを0に初期化します。
• 指定された数が素数であるかどうかをチェックする関数を記述します。
• 数値が賢いかどうかをチェックする関数を作成します。
• 最初のスマート番号が30であるため、30から繰り返すループを記述します。
  • 素数関数を使用して、現在の番号がスマート番号であるかどうかを確認します。
  • スマートな数字を見つけたら、カウントを1つ増やします。
  • カウントがNに等しい場合は、スマート番号を返します。

実装

以下は、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;
}

出力

上記のコードを実行すると、次の結果が得られます。

174