C++での等デジタル数

等デジタル数は数学的に特殊な数であり、数の桁数は素因数分解の数と同じです。

この問題では、整数値nが与えられます。私たちの仕事は、nまでのすべての等デジタル数に対するプログラムを作成することです。

問題を理解するために例を見てみましょう

入力： n =12

出力：1 2 3 5 7 10 11

ソリューションアプローチ：

この問題の簡単な解決策は、数の因数を見つけて、素数の数が数の桁数と等しいかどうかを確認することです。

主な要因は、ふるい法を使用して見つけることができます。

アルゴリズム：

ステップ1： すべての素数を見つけます。
ステップ2： 数nの桁数を数えます。

ステップ3： 数のすべての素因数を見つけて、その中の桁数を数えます。

ステップ4： 両方の値を比較します。
ステップ5： trueの場合は数値を返します。

ソリューションの動作を説明するプログラム

例

#include<bits/stdc++.h>
using namespace std;
const int MAX = 10000;

vector <int> primes;

void findAllPrimes()
{
   bool marked[MAX/2 + 1] = {0};
   for (int i=1; i*i<= (MAX -1)/2; i++)
      for (int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1)
         marked[j] = true;
   primes.push_back(2);
   for (int i=1; i<=MAX/2; i++)
      if (marked[i] == false)
         primes.push_back(2*i + 1);
}

bool isEquidigital(int n) {
   
   if (n == 1)
      return true;
   int number = n;
   int digitSum = 0;
   while (number > 0)
   {
      digitSum++;
      number = number/10;
   }
   int primeDigits = 0 , expCount = 0, p;
   for (int i = 0; primes[i] <= n/2; i++) {
      while (n % primes[i] == 0) {
         p = primes[i];
         n = n/p;
         expCount++;
      }
      while (p > 0) {
         primeDigits++;
         p = p / 10;
      }
      while (expCount > 1) {
         primeDigits++;
         expCount = expCount / 10;
      }
   }
   if (n != 1)
   {
      while (n > 0)
      {
         primeDigits++;
         n = n/10;
      }
   }

   return (primeDigits == digitSum);
}

int main() {

   findAllPrimes();
   int n = 11;
   cout << "Printing Equidigital Numbers less than "<<n<<" : ";
   for (int i=1; i<n; i++)
      if (isEquidigital(i))
         cout<<i<<"\t";
   return 0;
}

出力-

Printing Equidigital Numbers less than 11 : 1 2 3 5 7 10 11