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