En C++, la traduction de « nombre frugal » est « nombre frugal »

Dans ce problème, nous obtenons un entier positif N. Notre tâche est de créer un programme qui vérifie si un nombre donné est un nombre économe.

NOMBRE FRUGAL - Un nombre dont les chiffres sont strictement supérieurs au nombre de chiffres dans la factorisation première du nombre donné.

Exemple - 625, le facteur premier du nombre 625 est 5⁴.

Le nombre de chiffres dans 625 est 3.

5^{4 vaut 2.}

3 est strictement supérieur à 2. Par conséquent, 625 est un nombre économe.

Les premiers nombres frugaux sont - 125, 128, 243, 256, 343, 512, 625 etc.

Prenons un exemple pour comprendre le problème

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

Un des problèmes La solution est de vérifier si le nombre n actuel est un nombre parcimonieux. Pour ce faire, nous trouverons les facteurs premiers de n et calculerons le nombre de chiffres dans la factorisation, puis calculerons le nombre de chiffres dans ce nombre. Si le nombre de chiffres du nombre est supérieur au nombre de chiffres des facteurs, alors le nombre est un nombre parcimonieux, sinon il ne l'est pas.

Exemple

Programme qui illustre le fonctionnement de notre solution

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

Sortie

The number 625 is a Frugal number

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!