Số tiết kiệm trong C ++

Trong bài toán này, chúng ta được cung cấp một số nguyên dương N. Nhiệm vụ của chúng ta là tạo một chương trình để kiểm tra xem số đã cho có phải là Số tiết kiệm hay không.

SỐ NGỮ PHÁP - Một số có số chữ số của nó lớn hơn số chữ số trong phân tử nguyên tố của một số đã cho.

Ví dụ - 625, thừa số nguyên tố của số 625 là 5 ⁴ .

Số chữ số trong 625 là 3.

Số chữ số trong 5 ⁴ là 2.

3 lớn hơn 2. Do đó, 625 là một con số tiết kiệm.

Số tiết kiệm đầu tiên là - 125, 128, 243, 256, 343, 512, 625, v.v.

Hãy lấy một ví dụ để hiểu vấn đề

Input: n = 128
Output: Frugal number
Explanation :
Factors of 128 are 2^7, number of digits 2.
The number of digits in 128 is 3.
The number is a frugal number.

Phương pháp tiếp cận giải pháp

Một giải pháp cho vấn đề là kiểm tra xem số n hiện tại có phải là một số tiết kiệm hay không. Đối với điều này, chúng ta sẽ tìm các thừa số nguyên tố của n và đếm số chữ số trong phân thừa và sau đó đếm số chữ số trong số đó. Nếu số chữ số trong số lớn hơn số trong thừa số, thì số đó là một số thanh đạm, ngược lại thì không.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#include <bits/stdc++.h>
using namespace std;

vector<long int> calcPrimeNum(long int n){

   bool primeNos[n + 1];
   memset(primeNos, true, sizeof(primeNos));
   for (int i = 2; i * i <= n; i++) {
      if (primeNos[i] == true) {
         for (int j = i * 2; j <= n; j += i)
            primeNos[j] = false;
      }
   }
   vector<long int> allPrimeNumbers;
   for (int i = 2; i < n; i++)
      if (primeNos[i])
         allPrimeNumbers.push_back(i);
   return allPrimeNumbers;
}
int countNumDigits(long int n){

   long long int num = n;
   int digitCount = 0;
   while (num != 0) {
      num = num / 10;
      digitCount++;
   }
   return digitCount;
}
bool isFrugalNum(long int n){

   vector<long int> primeNum = calcPrimeNum(n);
   long int num = n;
   long int factorDigitCount = 0;
   for (int i = 0; i < primeNum.size(); i++) {
      if (num % primeNum[i] == 0) {
         long int k = 0;
         while (num % primeNum[i] == 0) {
            num = num / primeNum[i];
            k++;
         }
         if (k == 1)
            factorDigitCount = factorDigitCount + countNumDigits(primeNum[i]);
         else if (k != 1)
            factorDigitCount = factorDigitCount + countNumDigits(primeNum[i]) +                               countNumDigits(k);
      }
   }
   return (countNumDigits(n) > factorDigitCount && factorDigitCount != 0);
}
int main(){

   long int n = 625;
   cout<<"The number "<<n<<" is ";isFrugalNum(n)? cout<<"a Frugal number\n" : cout << "not a Frugal number\n";
   return 0;
}

Đầu ra

The number 625 is a Frugal number