In C++, the translation of "Frugal Number" is "frugal number"

In this problem, we get a positive integer N. Our task is to create a program that checks if a given number is a frugal number.

FRUGAL NUMBER - A number whose digits are strictly greater than the number of digits in the prime factorization of the given number.

Example - 625. The prime factors of the number 625 are 5⁴.

The number of digits in 625 is 3.

5^{4 is 2.}

3 is strictly greater than 2. Therefore, 625 is a frugal number.

The first few frugal numbers are - 125, 128, 243, 256, 343, 512, 625, etc.

Let’s take an example to understand Problem

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.

Solution

One solution to this problem is to check if the current number n is a frugal number. To do this, we will find the prime factors of n and count the number of digits in the factorization, then calculate the number of digits in that number. A number is a parsimonious number if the number of digits in it is greater than the number of digits in the factors, otherwise it is not.

Example

Program illustrating how our solution works

#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;
}

Output

The number 625 is a Frugal number

The above is the detailed content of In C++, the translation of "Frugal Number" is "frugal number". For more information, please follow other related articles on the PHP Chinese website!